Valid Sudoku

A cell breaks the board exactly when its digit already appears in its row, its column, or its 3x3 box. Checking that “already appears” question with a fresh scan every time is wasteful — a set per row, per column, and per box lets every cell answer it in O(1), all in a single pass over the board.

Brute Force

Time O(1) — O(n³) for a general n x n boardSpace O(1)

For each filled cell, rescan its entire row, column, and box looking for a duplicate of its value.

class Solution:
    def isValidSudoku(self, board: list[list[str]]) -> bool:
        for r in range(9):
            for c in range(9):
                val = board[r][c]
                if val == ".":
                    continue
                for k in range(9):
                    if k != c and board[r][k] == val:
                        return False
                    if k != r and board[k][c] == val:
                        return False
                box_r, box_c = 3 * (r // 3), 3 * (c // 3)
                for i in range(box_r, box_r + 3):
                    for j in range(box_c, box_c + 3):
                        if (i, j) != (r, c) and board[i][j] == val:
                            return False
        return True

Since the board is fixed at 9x9, this is technically constant time, but it is the same repeated-rescan pattern that would blow up to O(n) work per cell (O(n³) overall) on a general n x n board — every cell triggers three fresh linear scans instead of remembering what has already been seen.

One Pass with Hash Sets

OptimalTime O(1) — O(n²) for a general n x n boardSpace O(1) — O(n²) general

Keep one set per row, one per column, and one per 3x3 box (indexed (r // 3) * 3 + c // 3). Walk the board once; for each filled cell, check all three sets before adding the digit to each of them. Any hit means a repeat.

class Solution:
    def isValidSudoku(self, board: list[list[str]]) -> bool:
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]

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

The three sets are all checked and updated together on every cell. The trace below replays the algorithm on the invalid board from Example 2 — where the top-left corner 5 was changed to 8 — showing each filled cell checked against its row, column, and 3x3 box set at once, until the box set trips on the duplicate:

scanning (0, 0) = 8 · box 0

Row 0 set

Column 0 set

Box 0 set

1 / 9

currentseenresultcomparing

Cell (0,0) holds 8. Row 0, column 0 and box 0 sets are all empty, so none contains 8. Insert 8 into all three.

Correctness: a board is valid exactly when no digit repeats within any row, column, or box. Checking the three matching sets before writing to them catches a repeat the moment it appears, in whichever dimension it occurs, and adding the digit afterward keeps the sets accurate for later cells.

Complexity: every one of the 81 cells is visited once, doing O(1) set lookups and inserts — constant work for a fixed 9x9 board. Written generally for an n x n board (n a perfect square), this is O(n²) time (one pass over all cells) and O(n²) space (the sets together hold at most one entry per cell).

Brute Force

One Pass with Hash Sets

More Arrays & Hashing practice