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 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Steps

1. Check Rows: Iterate through each row and use a set to check for duplicates. If a duplicate is found, the Sudoku is invalid.
2. Check Columns: Iterate through each column and use a set to check for duplicates. If a duplicate is found, the Sudoku is invalid.
3. Check 3x3 Sub-boxes: Iterate through each 3x3 sub-box. Calculate the starting row and column indices for each sub-box. Iterate through the cells in the sub-box and use a set to check for duplicates. If a duplicate is found, the Sudoku is invalid.
4. Return True: If all checks pass without finding any duplicates, the Sudoku is valid, and the function returns True.

Explanation

The solution utilizes sets to efficiently check for duplicates. Sets only allow unique elements, so adding an element that already exists will not change the set's size. We leverage this property to detect duplicates in rows, columns, and 3x3 sub-boxes. The code systematically checks each row, column, and sub-box for violations of the Sudoku rules.

Code

def isValidSudoku(board):
    """
    Checks if a 9x9 Sudoku board is valid.

    Args:
      board: A 9x9 list of lists representing the Sudoku board.

    Returns:
      True if the board is valid, False otherwise.
    """

    # Check Rows
    for row in board:
        seen = set()
        for num in row:
            if num != '.' and num in seen:
                return False
            if num != '.':
                seen.add(num)

    # Check Columns
    for col in range(9):
        seen = set()
        for row in range(9):
            num = board[row][col]
            if num != '.' and num in seen:
                return False
            if num != '.':
                seen.add(num)

    # Check 3x3 Sub-boxes
    for box_row in range(0, 9, 3):
        for box_col in range(0, 9, 3):
            seen = set()
            for row in range(box_row, box_row + 3):
                for col in range(box_col, box_col + 3):
                    num = board[row][col]
                    if num != '.' and num in seen:
                        return False
                    if num != '.':
                        seen.add(num)

    return True

Complexity

• Time Complexity: O(n^2), where n is the size of the board (9 in this case). We iterate through the board three times (rows, columns, and sub-boxes). The set operations have an average time complexity of O(1).

• Space Complexity: O(n), where n is the size of the board. The space used is primarily for the sets used to track seen numbers in each row, column, and sub-box. The space used by the sets is proportional to the number of cells in a row, column, or sub-box.