LeetCode #36 Medium

Valid Sudoku

Decide whether a partially filled 9x9 Sudoku board breaks any row, column or 3x3 box rule.

arrayhash-tablematrix

02

Intuition

💡

Rows and columns are easy and you will get them right on the first try. The box index is where this problem actually lives, and the natural guess r // 3 + c // 3 is wrong in a way that hides: it collides. Cell (0,3) sits in the top-middle box and gives 1; cell (3,0) sits in the middle-left box and also gives 1, so two unrelated boxes share one set and your code reports conflicts that do not exist. The formula must be (r // 3) * 3 + c // 3, which multiplies the row band by 3 first so the nine boxes land on 0 through 8 with no overlap at all. The second thing to hold onto is that a dot is never a violation: you are validating what is written, not proving the puzzle solvable, so skip empty cells outright rather than trying to reason about them. The invariant is that after processing any cell, the three sets contain exactly the digits seen so far in that cell's row, column and box, so a duplicate is detected the instant it is written.

03

Approach

1

One pass, three families of sets

You do not need three separate scans over the board. A single traversal can file each digit into its row set, its column set and its box set at the same moment, because those three memberships are all determined by the same (r, c). Keeping nine sets per family, or one dictionary keyed by a string like 'r3:7', both work; the key point is that all three checks happen before any of the three insertions.

2

Derive the box index correctly

Integer-divide the row by 3 to get the box row band 0 to 2, integer-divide the column by 3 to get the box column band 0 to 2, then flatten those two coordinates into one number with (r // 3) * 3 + c // 3. This is the standard row-major flattening of a 3x3 layout, and the multiply is exactly what prevents the (0,3) versus (3,0) collision that plain addition produces.

3

Skip dots, and fail fast on the first duplicate

An empty cell contributes nothing and can never conflict, so continue past it immediately. When a digit is already present in any of its three sets, return False right away. Validity is a conjunction over every cell, so no later cell can undo a violation, and stopping early saves the rest of the scan on invalid boards.

04

Solution & live demo

python

▶1class Solution:
▶2    def isValidSudoku(self, board: List[List[str]]) -> bool:
▶3        rows = [set() for _ in range(9)]
▶4        cols = [set() for _ in range(9)]
▶5        boxes = [set() for _ in range(9)]
▶6        for r in range(9):
▶7            for c in range(9):
▶8                ch = board[r][c]
▶9                if ch == '.':
▶10                    continue
▶11                b = (r // 3) * 3 + c // 3
▶12                if ch in rows[r] or ch in cols[c] or ch in boxes[b]:
▶13                    return False
▶14                rows[r].add(ch)
▶15                cols[c].add(ch)
▶16                boxes[b].add(ch)
▶17        return True

05

Edge cases

Completely empty board (all dots)

Nothing is ever inserted, no conflict is possible, and the answer is True.

Duplicate inside a box but not in any row or column

Only the box set catches it, which is precisely the case the broken r // 3 + c // 3 formula gets wrong.

Valid but unsolvable board

Still returns True; the problem asks about the rules as written, not about solvability.

Duplicate in the very first row

Detected on the second occurrence and returns False without scanning the remaining rows.

06

Complexity

Time

O(1)

Space

O(1)

The board is fixed at 81 cells, so both bounds are constant; on a general n x n board it would be O(n^2) time and space.