Valid Sudoku · DSA Prep

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) — really O(n²) per cell, n=9Space 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 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 row, column, and box sets are all updated together on every cell, but to keep the trace readable, here is just the box-0 set (the top-left 3x3 sub-box) while scanning its 9 cells of the invalid board from Example 2 — where the top-left corner was changed from 5 to 8:

cell = (0,0)

Hash Map

8 → seen in box 0

1 / 5

comparingcurrent

(0,0)=8 is not in box 0 yet. Add it to the box set (and its row/col sets, not shown).

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 divisible by 3), this is O(n²) time (one pass over all cells) and O(n²) space (the sets together hold at most one entry per cell).