Valid Sudoku (LeetCode 36)

The problem

You get a 9×9 Sudoku board as a list of lists of strings. Each cell is a digit '1'–'9' or '.' for empty. Return True if the filled cells break none of the three rules:

• no digit repeats in any row;
• no digit repeats in any column;
• no digit repeats in any of the nine 3×3 boxes.

You don’t have to check that the puzzle can be solved, only that what’s there is consistent.

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

Output: True

Change the top-left 5 to 8 and the answer becomes False: the top-left box would then hold two 8s.

How to think about it

Start with brute force. Check the rules separately: for each of the 9 rows, collect its digits and look for a repeat; do the same for the 9 columns and the 9 boxes. That’s 27 groups of 9 cells, three passes over the board. It’s correct and already cheap, but it means writing three nearly identical loops, and the box loop is easy to get wrong.

The key insight: every rule is “have I seen this before?” in some group. A digit in cell (r, c) belongs to exactly three groups: row r, column c, and box (r // 3, c // 3). So for each filled cell, build three keys that name the group and the digit, and put them in one set. If any key is already in the set, that digit has appeared twice in that group.

Make the keys impossible to confuse. The code uses (r, 'r', v) for rows, ('c', c, v) for columns and (r // 3, c // 3, v) for boxes. The string sits in a different position in each shape, so a row key can never equal a column or box key. r // 3 and c // 3 map each cell to one of the boxes (0, 0) to (2, 2).

Which pattern is this? Hash set membership with composite keys. The tell is “no duplicates within several overlapping groups”.

Approach

1. Create an empty set seen.
2. Walk every cell (r, c). Skip it if it’s '.'.
3. Build its three keys: row, column and box, each including the digit v.
4. If any key is already in seen, return False. Otherwise add it.
5. If the walk finishes, return True.

Solution

def is_valid_sudoku(board):
    seen = set()
    for r in range(9):
        for c in range(9):
            v = board[r][c]
            if v == '.': continue
            keys = [(r, 'r', v), ('c', c, v), (r//3, c//3, v)]   # row, column, box
            for key in keys:
                if key in seen: return False                    # repeat in that group
                seen.add(key)
    return True
# is_valid_sudoku(valid_board) -> True

Dry run

The first filled cells of the example board, then the cell where the modified board (top-left changed to 8) fails:

In the modified board, (0, 0) added the box key (0, 0, '8'). The 8 at (2, 2) is in the same box, so its box key repeats.

Complexity

• Time: O(1). The board is always 81 cells with 3 keys each. For a general n×n board it’s O(n²).
• Space: O(1). At most 243 keys. O(n²) for the general case.

Edge cases and pitfalls

• Empty board: no keys are ever added, so it returns True.
• Valid ≠ solvable. A board can pass this check and still have no solution. Don’t try to solve it.
• Wrong box index. The box is (r // 3, c // 3), not r // 3 + c // 3 (which collides different boxes) or r % 3.
• Ambiguous keys: a key like (r, v) for rows and (c, v) for columns would collide (row 2 and column 2). Tag each kind of key.
• Digits are strings. Compare with '.', not 0 or None.

Related problems

• Contains Duplicate (LeetCode 217): the one-group version of this check.
• N-Queens (LeetCode 51/52): sets of “used” rows, columns and diagonals, used while backtracking.
• Set Matrix Zeroes (LeetCode 73): another grid problem driven by row and column bookkeeping.