Valid Sudoku

Problem

You’re given a 9×9 Sudoku board where each cell holds a digit character "1"–"9" or "." for empty. Decide whether the board’s current filled cells are consistent with the rules:

1. No digit repeats within a row.
2. No digit repeats within a column.
3. No digit repeats within any of the nine 3×3 sub-boxes.

Only validate what’s filled in — the board does not need to be solvable or complete; empty cells are ignored.

Examples

Example 1:

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

→ True — no row, column, or box has a repeated digit.

Example 2: the same board with the top-left 5 changed to 8 → False Column 0 now holds two 8s (rows 0 and 3), and the top-left 3×3 box also gets two 8s.

Example 3: a board whose row 4 is 1 . . . 1 . . . . (all else empty) → False — duplicate 1 in one row.

Constraints

• The board is always 9×9; cells are "1"–"9" or ".".

The input size is fixed, so everything is technically O(1) — the exercise is doing it in one pass with clean bookkeeping instead of 27 separate scans.

Think about it first

TL;DR

Single pass with hash sets per row/column/box — O(n²) time, O(n²) space for an n×n board (n = 9, so constant in practice).

Approach 1 — Brute force (re-scan each unit per cell)

The naive intuition: for every filled cell, scan its entire row, its entire column, and its entire 3×3 box looking for another cell with the same digit.

from typing import List


class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        for r in range(9):
            for c in range(9):
                d = board[r][c]
                if d == ".":
                    continue
                for j in range(9):                    # row scan
                    if j != c and board[r][j] == d:
                        return False
                for i in range(9):                    # column scan
                    if i != r and board[i][c] == d:
                        return False
                br, bc = 3 * (r // 3), 3 * (c // 3)   # box scan
                for i in range(br, br + 3):
                    for j in range(bc, bc + 3):
                        if (i, j) != (r, c) and board[i][j] == d:
                            return False
        return True

Complexity: O(n³) for an n×n board (each of the n² cells rescans O(n) cells), O(1) space. At n = 9 this is only ~2,000 comparisons — nothing “kills” it at this fixed size; what it costs you is elegance and scalability, and it re-reads every unit 9 times instead of once.

Approach 2 — One pass with hash sets

The insight: each cell belongs to exactly one row, one column, and one box, and “no duplicates in a group” is exactly what a hash set checks in O(1). Keep 27 sets (9 rows, 9 columns, 9 boxes), visit each cell once, and fail the moment a digit re-enters any of its three groups. The box index flattens to (r // 3) * 3 + c // 3.

from typing import List
from collections import defaultdict


class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows: defaultdict[int, set[str]] = defaultdict(set)
        cols: defaultdict[int, set[str]] = defaultdict(set)
        boxes: defaultdict[int, set[str]] = defaultdict(set)

        for r in range(9):
            for c in range(9):
                d = board[r][c]
                if d == ".":
                    continue
                b = (r // 3) * 3 + c // 3
                if d in rows[r] or d in cols[c] or d in boxes[b]:
                    return False
                rows[r].add(d)
                cols[c].add(d)
                boxes[b].add(d)
        return True

Walkthrough on Example 2 (Example 1’s board with the top-left 5 replaced by 8):

1. (0,0) = “8”: box 0. All sets empty → add. rows[0] = {8}, cols[0] = {8}, boxes[0] = {8}.
2. (0,1) = “3”: new everywhere → add. (0,4) = “7”, (1,0) = “6”, (1,3) = “1”, … each first occurrence in its row/col/box → added.
3. (2,1) = “9”: rows[2], cols[1], boxes[0] don’t contain “9” → add (boxes[0] is now {8, 6, 9} after row 1’s “6”… plus “8” from step 1).
4. (3,0) = “8”: row 3 fresh, but cols[0] already contains “8” (from step 1) → return False. ✓

(The box check would not have fired here — (3,0) is in box 3 — which is why all three group checks are needed.)

Complexity: O(n²) time — each of the n² cells does O(1) set work; O(n²) space across the 27 sets. For the fixed 9×9 board: 81 steps.

Approach 3 — Bitmasks instead of sets

The insight: each group only tracks membership of digits 1–9 — nine booleans — so an int used as a bitmask (bit d set ⇔ digit d seen) replaces each hash set, with & as the membership test and | as insert. Same algorithm, denser bookkeeping; this is the version to mention when asked about minimizing constant factors/memory.

from typing import List


class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [0] * 9
        cols = [0] * 9
        boxes = [0] * 9

        for r in range(9):
            for c in range(9):
                ch = board[r][c]
                if ch == ".":
                    continue
                bit = 1 << (int(ch) - 1)
                b = (r // 3) * 3 + c // 3
                if (rows[r] | cols[c] | boxes[b]) & bit:
                    return False
                rows[r] |= bit
                cols[c] |= bit
                boxes[b] |= bit
        return True

Walkthrough on Example 3 (row 4 = 1 . . . 1 . . . ., all else empty):

1. (4,0) = “1”: bit = 0b1. rows[4] = 0 → no hit; set rows[4] = 0b1, cols[0] = 0b1, boxes[3] = 0b1.
2. (4,4) = “1”: bit = 0b1. rows[4] & 0b1 is nonzero → return False. ✓

Complexity: O(n²) time, O(n) space (27 machine ints).

Common pitfalls

• Wrong box index: it’s (r // 3) * 3 + c // 3 — mixing up which coordinate is multiplied by 3 maps cells to the wrong box and lets diagonal duplicates slip through.
• Forgetting to skip "." — empties would register as “duplicates” instantly.
• Validating only rows and columns; box violations (Example 2’s two 8s meet in a box on other boards) are the ones brute-row/col checks miss.
• Testing solvability or completeness — the problem asks only whether the placed digits conflict.

Pattern takeaway

When an object must satisfy several “no duplicates within a group” constraints at once, give each group its own hash set (or bitmask) and stream the elements through all of their groups in a single pass — membership checks make each constraint O(1). The only real design work is a clean formula mapping an element to its group ids, like (r // 3) * 3 + c // 3 here.