LeetCode Solutions Blog

Valid Sudoku

Number: 36

Difficulty: Medium

Paid? No

Problem Description

Determine if a given 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the rules that each row, column, and each of the nine 3x3 sub-boxes must contain the digits 1-9 without repetition.

Key Insights

Validate each row by checking for duplicate numbers while ignoring empty cells.
Validate each column in the same way.
Divide the board into nine 3x3 sub-boxes and check each for duplicate numbers.
Use hash sets (or equivalent data structures) to keep track of seen digits for rows, columns, and boxes.
The board size is fixed (9x9), so the overall time complexity is constant with respect to input size.

Space and Time Complexity

Time Complexity: O(1) — Since the board size is fixed at 9x9. Space Complexity: O(1) — The extra space used by the sets is bounded by the fixed board size.

Solution

The solution uses three main data structures: an array of sets for rows, an array of sets for columns, and an array of sets for 3x3 sub-boxes. For each cell, if it is not empty, check if the number is already present in the corresponding row, column, or box. If found, return false immediately. Otherwise, add the number to the respective sets. Compute the index for the 3x3 sub-box using the formula: (row_index // 3) * 3 + (col_index // 3). If no duplicates are found after traversing the entire board, the board is considered valid.

Code Solutions

# Python solution with inline comments
def isValidSudoku(board):
    # Initialize sets for rows, columns, and boxes
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    
    # Iterate over each cell in the board
    for r in range(9):
        for c in range(9):
            num = board[r][c]
            # Skip empty cells
            if num == '.':
                continue
            # Compute box index using integer division
            box_index = (r // 3) * 3 + (c // 3)
            # Check if the number is already present in the row, column, or box
            if num in rows[r] or num in cols[c] or num in boxes[box_index]:
                return False
            # Add number to row, column, and box sets
            rows[r].add(num)
            cols[c].add(num)
            boxes[box_index].add(num)
    
    return True

# Example usage:
if __name__ == "__main__":
    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"]
    ]
    print(isValidSudoku(board))  # Expected output: True