Valid Sudoku medium

Problem Statement

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable. Only the filled cells need to be validated.

Example 1

Input: board = [["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"]] Output: true

Example 2

Input: board = [["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"]] Output: false Explanation: Same as Example 1, except with the 8 in the top left is not valid.

Steps

1. Create helper functions: We'll need functions to check rows, columns, and 3x3 subgrids.
2. Iterate through the board: We'll traverse the board cell by cell.
3. Check for validity: For each filled cell (not "."), we'll check if it's valid using our helper functions.
4. Return the result: If any cell is invalid, return false; otherwise, return true.

Explanation

The solution uses three helper functions: isValidRow, isValidCol, and isValidSubgrid. Each function checks for duplicates within its respective scope (row, column, or 3x3 subgrid). The main function iterates through the board, and for each non-empty cell, it calls all three helper functions. If any of them return false, it means a rule is violated, and the function immediately returns false. If the loop completes without finding any violations, it means the Sudoku board is valid, and the function returns true. The use of sets makes duplicate checking efficient (O(1) on average).

Code

function isValidSudoku(board: string[][]): boolean {
    // Helper function to check if a row is valid
    const isValidRow = (row: string[]): boolean => {
        const seen = new Set();
        for (const num of row) {
            if (num !== '.' && seen.has(num)) return false;
            seen.add(num);
        }
        return true;
    };

    // Helper function to check if a column is valid
    const isValidCol = (colIndex: number): boolean => {
        const seen = new Set();
        for (let i = 0; i < 9; i++) {
            const num = board[i][colIndex];
            if (num !== '.' && seen.has(num)) return false;
            seen.add(num);
        }
        return true;
    };

    // Helper function to check if a 3x3 subgrid is valid
    const isValidSubgrid = (rowStart: number, colStart: number): boolean => {
        const seen = new Set();
        for (let i = rowStart; i < rowStart + 3; i++) {
            for (let j = colStart; j < colStart + 3; j++) {
                const num = board[i][j];
                if (num !== '.' && seen.has(num)) return false;
                seen.add(num);
            }
        }
        return true;
    };

    // Iterate through the board and check for validity
    for (let i = 0; i < 9; i++) {
        if (!isValidRow(board[i]) || !isValidCol(i) || !isValidSubgrid(Math.floor(i / 3) * 3, (i % 3) * 3)) {
            return false;
        }
    }

    return true;
}

Complexity

• Time Complexity: O(n), where n is the number of cells in the board (81). We iterate through the board once. Set operations are O(1) on average.
• Space Complexity: O(1). The space used by the sets is constant because they only store at most 9 numbers.