Valid Sudoku — Solution

Problem

Given a 9×9 Sudoku board filled with digits 1–9 and dots for empty cells, decide whether it's currently valid. A board is valid if every row, every column, and every 3×3 sub-box contains each digit at most once — you only check the filled cells, not whether the puzzle is actually solvable.

• Input: the board above
• Output: true
• Explanation: no digit repeats in any row, column, or 3×3 box

Counter-example: if the top-left box contained two 5s (e.g., a second 5 at row 1, col 0), the board would be invalid even if every row and column still looked clean individually.

Intuition

Because the board is always 9×9, every operation here is constant-time — correctness is the only challenge. The key insight is that all three constraint types (rows, columns, 3×3 boxes) can be validated in a single left-to-right, top-to-bottom pass: maintain one hash set per row, column, and box, and whenever you encounter a filled cell, check its digit against all three sets before recording it.

Solution — Single-Pass Hash Sets

Allocate three arrays of nine sets each — one array for rows, one for columns, one for boxes. Scan every cell; if a digit is already in any of its corresponding sets, the board is invalid.

1. Create row_sets[9], col_sets[9], and box_sets[9], each containing empty sets.
2. Iterate over all 81 cells row by row, left to right.
3. Skip any cell whose value is '.'.
4. Compute box_index = (row // 3) * 3 + (col // 3) — this maps each cell to one of nine boxes numbered 0–8.
5. If the digit already exists in row_sets[row], col_sets[col], or box_sets[box_index], return false.
6. Otherwise add the digit to all three sets and continue.
7. Return true after scanning all cells without conflict.

1def isValidSudoku(board: list[list[str]]) -> bool:
2    row_sets = [set() for _ in range(9)]
3    col_sets = [set() for _ in range(9)]
4    box_sets = [set() for _ in range(9)]
5
6    for row in range(9):
7        for col in range(9):
8            digit = board[row][col]
9            if digit == '.':
10                continue
11
12            # maps each cell to one of nine 3×3 boxes (0 = top-left, 8 = bottom-right)
13            box_index = (row // 3) * 3 + (col // 3)
14
15            if (digit in row_sets[row]
16                    or digit in col_sets[col]
17                    or digit in box_sets[box_index]):
18                return False
19
20            row_sets[row].add(digit)
21            col_sets[col].add(digit)
22            box_sets[box_index].add(digit)
23
24    return True

Time: O(1) — the board is always 9×9, so we visit exactly 81 cells with constant work each.

Space: O(1) — 27 sets holding at most 9 digits each; the total never exceeds 243 entries.

Complexity Summary

Common Mistakes

• Swapping row and column in the box formula — (row // 3) * 3 + (col // 3) is correct; flipping to (col // 3) * 3 + (row // 3) produces the same nine integers but maps different cells to the same box, silently giving wrong answers on certain boards while passing others.
• Forgetting to skip '.' cells — adding the dot character to every row, column, and box set looks harmless until any board with two empty cells in the same row returns false.
• Checking only rows and columns — a board can satisfy the row and column constraints while having duplicate digits inside a 3×3 box; the box check is the constraint developers forget most often.
• Using a single set with string keys like "row:0:5" — this works but requires a strict separator; "row:1:2" and "row:12" collide without one, and the subtle bug only surfaces on boards with two-digit-adjacent row/col indices.
• Inserting before checking — if you add the digit first and then test whether the set grew, you lose the short-circuit and can't distinguish a fresh insertion from a duplicate.

Related Problems

• sudoku-solver — extend validation to backtracking-based board completion
• set-matrix-zeroes — track and apply a constraint across all rows and columns of a 2D matrix
• word-search — grid traversal with per-cell constraint enforcement
• contains-duplicate — fundamental duplicate detection using a hash set
• valid-anagram — character frequency validation using counting or sets