Valid Sudoku

PracticeNeetCode ↗LeetCode ↗

Determine if a 9×9 Sudoku board is valid: each row, each column, and each of the nine 3×3 sub-boxes must contain the digits 1–9 without repetition. Only the filled cells need checking — the board doesn't need to be solvable.

Example

Key Pointers

• Only three constraints matter: no repeat in a row, no repeat in a column, no repeat in a 3×3 box.
• The box-index formula (r // 3) * 3 + c // 3 maps any (row, col) to one of nine box ids, 0–8 — worth memorizing.
• One pass over all 81 cells is enough; there's no need to validate rows, then columns, then boxes separately.

Step-by-Step Analysis

1. Create 9 empty sets each for rows, cols, and boxes.
2. For each cell (r, c), skip it if the value is ".".
3. Compute the box index b = (r // 3) * 3 + c // 3.
4. If the digit is already in rows[r], cols[c], or boxes[b], return False; otherwise add it to all three.
5. If every cell passes, return True.

Complexity

Time: O(1) — the board is a fixed 81 cells — Space: O(1)

Code

def isValidSudoku(board: list[list[str]]) -> bool:
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]

    for r in range(9):
        for c in range(9):
            val = board[r][c]
            if val == ".":
                continue
            b = (r // 3) * 3 + c // 3
            if val in rows[r] or val in cols[c] or val in boxes[b]:
                return False
            rows[r].add(val)
            cols[c].add(val)
            boxes[b].add(val)

    return True

Code Explanation

How the solution above works, piece by piece.

1. Three lists of 9 sets: rows, cols and boxes, each remembering the digits seen in that row, column or box.
2. Visit all 81 cells; '.' means empty and is skipped.
3. b = (r // 3) * 3 + c // 3 numbers the 3×3 boxes 0–8: r // 3 picks the band of rows, c // 3 the band of columns.
4. If the digit is already in its row, column or box set, the board breaks a rule → False.
5. Otherwise add it to all three sets. The board is fixed at 9×9, so this is O(81) = O(1) time and space.

Visual Walkthrough

An example board where row 0 contains two 5s:

Video Explanation

NeetCode — LeetCode 36