Valid Sudoku Algo - Leetcode

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

1. 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

1. 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

1. 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.