LeetCode 036 - Valid Sudoku

2026-04-09

medium　array

You are given a 9 x 9 Sudoku board board. A Sudoku board is valid if the following rules are followed:

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

Return true if the Sudoku board is valid, otherwise return false

Note: A board does not need to be full or be solvable to be valid.

Example 1:

Input: board =
[["1","2",".",".","3",".",".",".","."],
 ["4",".",".","5",".",".",".",".","."],
 [".","9","8",".",".",".",".",".","3"],
 ["5",".",".",".","6",".",".",".","4"],
 [".",".",".","8",".","3",".",".","5"],
 ["7",".",".",".","2",".",".",".","6"],
 [".",".",".",".",".",".","2",".","."],
 [".",".",".","4","1","9",".",".","8"],
 [".",".",".",".","8",".",".","7","9"]]

Output: true

Example 2:

Input: board =
[["1","2",".",".","3",".",".",".","."],
 ["4",".",".","5",".",".",".",".","."],
 [".","9","1",".",".",".",".",".","3"],
 ["5",".",".",".","6",".",".",".","4"],
 [".",".",".","8",".","3",".",".","5"],
 ["7",".",".",".","2",".",".",".","6"],
 [".",".",".",".",".",".","2",".","."],
 [".",".",".","4","1","9",".",".","8"],
 [".",".",".",".","8",".",".","7","9"]]

Output: false

Explanation: There are two 1's in the top-left 3x3 sub-box.

Constraints:

board.length == 9board[i].length == 9board[i][j] is a digit 1-9 or '.'.

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit 1-9 or '.'.

Solution 1:

class Solution:
    def isValidSudoku(self, board: list[list[str]]) -> bool:
        # Brute-force Solution
        # We validate the Sudoku board by checking three main rules independently.
        # Note: Since the board is strictly 9x9, the strict Time and Space complexity is O(1).
        # If generalized for an N x N board, it would be Time: O(N^2) and Space: O(N).

        # 1. Check if each row is valid (no duplicate digits from 1-9)
        for i in board:
            digit_set = set()
            for j in i:
                if j == ".":
                    continue
                # If the digit is already in our set, the row is invalid
                if j in digit_set:
                    return False
                digit_set.add(j)
                
        # 2. Check if each column is valid
        for i in range(9):
            digit_set = set()
            for j in range(9):
                # i represents the column index, j represents the row index
                if board[j][i] == ".":
                    continue
                if board[j][i] in digit_set:
                    return False
                digit_set.add(board[j][i])
                
        # 3. Check if each 3x3 sub-box is valid
        x = 0
        for _ in range(3):
            y = 0
            for _ in range(3):
                digit_set = set() # Use set instead of list for O(1) lookup time
                # Iterate through the specific 3x3 sub-box boundaries
                for i in range(x, x + 3):
                    for j in range(y, y + 3):
                        if board[i][j] == ".":
                            continue
                        if board[i][j] in digit_set:
                            return False
                        digit_set.add(board[i][j])
                # Move to the next 3x3 box in the same row block
                y += 3
            # Move down to the next row block of 3x3 boxes
            x += 3
            
        # If all checks pass, the board is valid
        return True

Solution 2:

from collections import defaultdict

class Solution:
    def isValidSudoku(self, board: list[list[str]]) -> bool:
        # Optimal One-Pass Solution
        # We use hash sets to keep track of the digits we've seen in each row, column, and 3x3 box.
        # This allows us to validate the board by iterating through it only exactly once.
        
        # Time Complexity: O(1) strictly since the board is always 9x9. 
        # (Or O(N^2) if generalized to an N x N board).
        # Space Complexity: O(1) strictly, as the maximum number of elements in all sets combined is 81.
        
        # Initialize dictionaries where each key maps to a Set.
        # This prevents KeyError when we try to add or check items for the first time.
        rows = defaultdict(set)
        cols = defaultdict(set)
        boxes = defaultdict(set) # Key will be a tuple: (row // 3, col // 3)
        
        for r in range(9):
            for c in range(9):
                current_val = board[r][c]
                
                # Skip empty cells
                if current_val == ".":
                    continue
                    
                # Check if the current value already exists in the corresponding row, col, or box
                if (current_val in rows[r] or 
                    current_val in cols[c] or 
                    current_val in boxes[(r // 3, c // 3)]):
                    return False # Found a duplicate, invalid Sudoku!
                
                # If not found, add the value to our tracker sets
                rows[r].add(current_val)
                cols[c].add(current_val)
                boxes[(r // 3, c // 3)].add(current_val)
                
        # If we successfully iterate through the entire board without conflicts, it's valid!
        return True

Takeaway

Validating the rows and columns is straightforward, but the 3×3 sub-box check is where this problem gets interesting.

In the brute-force solution, two coordinate pointers x and y are incremented across the grid to control the scanning boundary of each sub-box — functional, but verbose.

The optimal one-pass solution trades a bit of space for a much cleaner approach. By introducing collections.defaultdict(set) for each of the three constraint categories, and using the integer division trick (r // 3, c // 3) to map any 2D cell coordinate to its corresponding sub-box index, we can validate all three rules simultaneously in a single pass.

This eliminates the nested boundary-control loops entirely and reduces the logic to one clean traversal — a great example of how the right data structure makes the algorithm self-evident.