36. Valid Sudoku — DSA Atlas

MediumArrays and HashingHash sets per row/column/boxConstraint tracking with sets

Valid Sudoku

Determine whether a partially filled 9x9 Sudoku board is valid. Only the filled cells (digits '1'-'9') need to be checked: no digit may repeat within any row, any column, or any of the nine 3x3 sub-boxes. Empty cells are marked '.' and the board need not be solvable.

Open official problem prompt ↗

In plain English

Confirm that the currently placed digits break none of Sudoku's three no-repeat rules, without needing to solve the puzzle.

Picture it like this

Like a proctor checking a seating chart: no two people with the same ID may share a row, a column, or a table cluster. You keep a checklist per row, per column, and per cluster and flag the first collision.

Example

Input: board = [["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
Why: No digit repeats in any row, column, or 3x3 box, so the board is valid.

Constraints

board.length == 9board[i].length == 9board[i][j] is a digit '1'-'9' or '.'Only filled cells are validated

Pattern lesson

See the pattern, then code

Constraint tracking with sets

↗

Arrays and Hashing

Duplicates, frequency counts, grouping, membership tests, or pair lookup.. Every filled cell belongs to exactly one row, one column, and one 3x3 box. Track seen digits for each of these 27 groups; the first time a digit reappears in any group its rule is broken.

New words, made simpleKnow these before the algorithm

Sub-box: One of the nine non-overlapping 3x3 regions that tile the board.
Box index: A number 0-8 identifying a cell's 3x3 region, computed from (row // 3) * 3 + col // 3.
Membership set: A hash set recording which digits have already appeared in a given group.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Recheck each group separately

Correct but traverses the board three times with more bookkeeping.

Loop rows, then columns, then boxes, scanning for duplicates in each.

Time O(1) fixed 9x9Space O(1)

Best choiceSingle pass, 27 sets

One traversal, clearest mapping of the three rules; recommended.

Maintain row, column, and box sets and validate every cell in one sweep.

Time O(1)Space O(1)

The rule we keep true

Invariant

After visiting a cell, rows[r], cols[c], and boxes[b] each contain exactly the filled digits seen so far in that row, column, and box, so any later duplicate is caught immediately.

Why this is correct

Reasoning

Each filled cell maps to a unique (row, column, box) triple. Storing its digit in all three sets means a rule violation — the same digit twice in one group — surfaces as a set membership hit the moment the second copy is examined, which is both necessary and sufficient for invalidity.

The algorithm in three movesSay these aloud before coding

1Create nine sets each for rows, columns, and boxes

cell (0,0)=5: rows[0]={5}, cols[0]={5}, box0={5}

2Scan every cell, skipping '.'

cell (0,1)=3: rows[0]={5,3}

3Compute the box index as (row // 3) * 3 + col // 3

cell (0,4)=7: rows[0]={5,3,7}, box1={7}

4If the digit is already in its row, column, or box set, return false; otherwise add it to all three

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readrow 0, col 0, box 0

2 · AskIs 5 already in any set?

3 · Update stateall empty

4 · ResultNo; add 5 to rows[0], cols[0], boxes[0]

Key takeaway

Digits from row 0 accumulate into that row's set while also updating their column and box sets.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-527 tracking sets
Nine sets each for rows, columns, and boxes hold the digits seen per group.
2
Lines 9-11Skip blanks, locate box
Empty cells impose no constraint; the box formula folds a 2D region into a single index 0-8.
3
Lines 12-16Check then record
A hit in any set means a repeat, so return false; otherwise register the digit in all three groups.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A completely empty board (all '.') is valid and returns true
A duplicate inside a 3x3 box even when its row and column are clean
A board that is valid but unsolvable — still returns true since solvability is not required

Common beginner mistakes

Miscomputing the box index, e.g. using row * 3 + col instead of the floor-division formula
Validating '.' cells as if they were digits
Forgetting one of the three group checks (a common bug is omitting the box test)

Check your understanding

Why is the box index (r // 3) * 3 + c // 3 rather than r // 3 + c // 3?

PyPython 3 · solution.py

Optimal

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                v = board[r][c]9                if v == ".":10                    continue11                b = (r // 3) * 3 + c // 312                if v in rows[r] or v in cols[c] or v in boxes[b]:13                    return False14                rows[r].add(v)15                cols[c].add(v)16                boxes[b].add(v)17        return True

Time complexityO(1)Optimized

Space complexityO(1)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonAppleMicrosoftUber

Valid Sudoku

Valid Sudoku

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Arrays and Hashing