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 board size is fixed at 9×9, so the work is technically O(1). The point of the exercise is to validate it in a single 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)

For every filled cell, scan its entire row, its column, and its 3×3 box for another cell holding the same digit.

from typing import List


def isValidSudoku(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 roughly 2,000 comparisons, so it runs fine at the fixed size. The cost is that it re-reads every row, column, and box nine times instead of once.

Approach 2 — One pass with hash sets

Each cell belongs to exactly one row, one column, and one box, and “no duplicates in a group” is precisely 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.

flowchart LR
  Cell["Cell (r, c) holds digit d"] --> Row["rows[r]"]
  Cell --> Col["cols[c]"]
  Cell --> Box["boxes[(r//3)*3 + c//3]"]

Each digit is checked against, and then added to, all three of its groups.

from typing import List
from collections import defaultdict


def isValidSudoku(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”, (2,1) = “9”, … each first occurrence in its row/col/box → added. boxes[0] is now {8, 3, 6, 9}.
3. (2,2) = “8”: boxes[0] already contains “8” (from step 1) → return False.

This board actually has two conflicts: two 8s in box 0 (cells (0,0) and (2,2)) and two 8s in column 0 (cells (0,0) and (3,0)). The row-major scan reaches the box duplicate at (2,2) first, so the box check fires before the scan ever gets to (3,0). Having all three group checks is what guarantees whichever conflict comes first is caught.

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


def isValidSudoku(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 and skipping the box check; a digit can be unique in its row and column yet still repeat inside its 3×3 box.
• 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.