Repost of https://dev.to/rhuzaifa/valid-sudoku-algo-leetcode-5f3h

So the other day I was doing some leetcode and found the Valid Sudoku problem interesting. Also since I had not posted for a long time (missed it 😁), thought why not just write how I solved, so here it goes.

Algorithm (I followed)

1. Map over each row of the board, check if row has duplicate numbers
2. Map over each column of the board, check if column has duplicate numbers
3. Map over each row of the board, if that row is the start of a unique 3x3 matrix, then create three 3x3 matrices and check for duplicates

We can check for each test case in a single map

Implementation (JavaScript)

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function (board) {
    // map over each row
    for (let row = 0; row < board.length; row++) {
        // we will store and check for dup digits
        const foundRowDigits = [];
        const foundColDigits = [];

        // map over each column
        for (let col = 0; col < board.length; col++) {
            const rowDigit = board[row][col]
            if (rowDigit !== '.') { // we are ignoring periods '.'
                // check duplicates in row
                if (foundRowDigits.includes(rowDigit)) {
                    // oh uh, dup found -> invalid sudoku
                    return false
                }

                foundRowDigits.push(rowDigit) // store row digit for further comparison
            }

            const colDigit = board[col][row]
            if (colDigit !== '.') { // we are ignoring periods '.'
                // check duplicates in row
                if (foundColDigits.includes(colDigit)) {
                    // oh uh, dup found -> invalid sudoku
                    return false
                }

                foundColDigits.push(colDigit) // store row digit for further comparison
            }
        }


        if (row % 3 === 0) { // row is the start of 3 3x3 matrices
            let threeByThreeGrid = [] // we will store grid values to check dups
            let rowIndex = row

            for (let colIndex = 0; colIndex < 9; colIndex += 3) {
                // make 3x3 grid by taking a rowIndex and colIndex
                for (let gridRowIndex = rowIndex; gridRowIndex < rowIndex + 3; gridRowIndex++) {
                    for (let gridColIndex = colIndex; gridColIndex < colIndex + 3; gridColIndex++) {
                        const digit = board[gridRowIndex][gridColIndex]
                        if (digit !== '.') { // we are ignoring periods '.'

                            // check if there are duplicates in a 3x3 matrix
                            if (threeByThreeGrid.includes(digit)) {
                                // oh uh, dup found -> invalid sudoku
                                return false
                            }

                            threeByThreeGrid.push(digit) // store row digit for further comparison
                        }
                    }
                }

                threeByThreeGrid = [] // reset the grid
            }
        }
    }

    return true // if above test cases passed then sudoku is valid
};

Time complexity

O(n^2) - We have 2 nested for loops. The 3x3 subgrids only work in certain cases so going for the worst case we have O(n^2)

Space complexity

O(1)

Test Cases

1. A valid sudoku

   const validSudoku = [
   ["5", "3", ".", ".", "7", ".", ".", ".", "."],
   ["6", ".", ".", "1", "9", "5", ".", ".", "."],
   [".", "9", "8", ".", ".", ".", ".", "6", "."],
   ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
   ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
   ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
   [".", "6", ".", ".", ".", ".", "2", "8", "."],
   [".", ".", ".", "4", "1", "9", ".", ".", "5"],
   [".", ".", ".", ".", "8", ".", ".", "7", "9"]
   ];
   console.log(isValidSudoku(validSudoku)) // true

2. A sudoku with dups in row

   const sudokuWithRowDups = [
   ["5", "3", ".", ".", "7", ".", ".", ".", "5"],
   ["6", ".", ".", "1", "9", "5", ".", ".", "."],
   [".", "9", "8", ".", ".", ".", ".", "6", "."],
   ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
   ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
   ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
   [".", "6", ".", ".", ".", ".", "2", "8", "."],
   [".", ".", ".", "4", "1", "9", ".", ".", "5"],
   [".", ".", ".", ".", "8", ".", ".", "7", "9"]
   ]
   console.log(isValidSudoku(sudokuWithRowDups)) // false

3. A sudoku with dups in col

   const sudokuWithColDups = [
   ["8", "3", ".", ".", "7", ".", ".", ".", "."],
   ["6", ".", ".", "1", "9", "5", ".", ".", "."],
   [".", "9", "8", ".", ".", ".", ".", "6", "."],
   ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
   ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
   ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
   [".", "6", ".", ".", ".", ".", "2", "8", "."],
   [".", ".", ".", "4", "1", "9", ".", ".", "5"],
   [".", ".", ".", ".", "8", ".", ".", "7", "9"]
   ]
   console.log(isValidSudoku(sudokuWithColDups)) // false

4. A sudoku with dups in 3x3 matrices

   const sudokuWith3x3GridDups = [
   [".", ".", ".", ".", "5", ".", ".", "1", "."],
   [".", "4", ".", "3", ".", ".", ".", ".", "."],
   [".", ".", ".", ".", ".", "3", ".", ".", "1"],
   ["8", ".", ".", ".", ".", ".", ".", "2", "."],
   [".", ".", "2", ".", "7", ".", ".", ".", "."],
   [".", "1", "5", ".", ".", ".", ".", ".", "."],
   [".", ".", ".", ".", ".", "2", ".", ".", "."],
   [".", "2", ".", "9", ".", ".", ".", ".", "."],
   [".", ".", "4", ".", ".", ".", ".", ".", "."]
   ]
   console.log(isValidSudoku(sudokuWith3x3GridDups)) // false

It may not be perfect, and can always be improved. Let me know your thoughts and thanks for reading.