Valid Sudoku

Valid Sudoku asks you only to check a board, not solve it. It is a clean exercise in using hash sets to detect duplicates across three different groupings at once.

The slow way first

You could, for every cell, rescan its entire row, its entire column, and its 3x3 box looking for a match. That is correct but wasteful — each of the 81 cells triggers another sweep of ~27 cells, and the bookkeeping is fiddly and easy to get wrong.

The better question: as I scan once, can I just remember every digit I have already placed in each row, column, and box? Then a duplicate is a single O(1) set lookup.

The idea: one set per row, column, and box

Keep three collections of sets:

• rows[r] — digits already seen in row r
• cols[c] — digits already seen in column c
• boxes[(r//3, c//3)] — digits already seen in that 3x3 box

The trick is the box key: integer-dividing both coordinates by 3 collapses every cell in a box to the same (r//3, c//3) pair. Scan the board once; for each filled cell, if its digit is already in any of those three sets, the board is invalid.

The key insight: we check the three sets before adding the digit, so the very first repeat we encounter ends the scan.

Walk through it

Step through the animation. The scan pointer moves across the top-left box. At (0,0) we record a 5 into its row, column, and box sets. We skip the empty cell at (0,1). At (0,2) we hit another 5 — and 5 is already in rows[0]. That lookup succeeds, so we return False and both 5s light up as the clash.

Pseudocode

make rows, cols, boxes  -> each maps a key to a set of digits
for each cell (r, c):
    v = board[r][c]
    if v is empty ("."): skip it
    box = (r // 3, c // 3)
    if v is in rows[r] or cols[c] or boxes[box]:
        return False                  # duplicate -> invalid
    add v to rows[r], cols[c], boxes[box]
return True                            # scanned everything, no clash

The Python solution

def is_valid_sudoku(board):
    from collections import defaultdict
    rows, cols = defaultdict(set), defaultdict(set)
    boxes = defaultdict(set)
    for r in range(9):
        for c in range(9):
            v = board[r][c]
            if v == ".":
                continue
            box = (r // 3, c // 3)
            if v in rows[r] or v in cols[c] or v in boxes[box]:
                return False
            rows[r].add(v)
            cols[c].add(v)
            boxes[box].add(v)
    return True

• defaultdict(set) gives every new key an empty set automatically, so we never check whether a row/col/box has been seen yet.
• box = (r // 3, c // 3) is the box key — every cell in the same 3x3 block maps to the same tuple.
• Line 11 is the heart of the check: three O(1) set lookups. If any succeeds, we have a duplicate.
• We .add(v) after the check, so a digit is never compared against itself.

Complexity

The board is a fixed 9x9, so this is constant work overall — but the shape is the lesson: one pass, three hash sets, O(1) duplicate detection.

When this pattern shows up

Practice