Valid Sudoku

Problem

You are given a 9 x 9 Sudoku board board. A Sudoku board is valid if the following rules are followed:

Each row must contain the digits 1-9 without duplicates.

Each column must contain the digits 1-9 without duplicates.

Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without duplicates.

Return true if the Sudoku board is valid, otherwise return false.

Note: A board does not need to be full or be solvable to be valid.

Example 1

Input: board =
[["1","2",".",".","3",".",".",".","."],
 ["4",".",".","5",".",".",".",".","."],
 [".","9","8",".",".",".",".",".","3"],
 ["5",".",".",".","6",".",".",".","4"],
 [".",".",".","8",".","3",".",".","5"],
 ["7",".",".",".","2",".",".",".","6"],
 [".",".",".",".",".",".","2",".","."],
 [".",".",".","4","1","9",".",".","8"],
 [".",".",".",".","8",".",".","7","9"]]
Output: true

Example 2

Input: board =
[["1","2",".",".","3",".",".",".","."],
 ["4",".",".","5",".",".",".",".","."],
 [".","9","1",".",".",".",".",".","3"],
 ["5",".",".",".","6",".",".",".","4"],
 [".",".",".","8",".","3",".",".","5"],
 ["7",".",".",".","2",".",".",".","6"],
 [".",".",".",".",".",".","2",".","."],
 [".",".",".","4","1","9",".",".","8"],
 [".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: There are two 1's in the top-left 3x3 sub-box.

Constraints

board.length == 9
board[i].length == 9
board[i][j] is a digit 1-9 or '.'.

Thinking

Brute force idea: collect the 27 groups (9 rows, 9 columns, 9 boxes) separately and check each one for duplicates. That’s already $O(81)$ , i.e. $O(1)$ for a fixed board (or $O(n^2)$ for an $n \times n$ board), so it’s not slow. What’s wrong with it is that it reads the board three times and the box loop is easy to get wrong.
Key insight: every cell (r, c) belongs to exactly one row, one column and one box, and the box can be computed directly: $\text{box} = (r \,/\!/\, 3) \cdot 3 + (c \,/\!/\, 3) \quad\text{or the pair}\quad (r \,/\!/\, 3,\ c \,/\!/\, 3)$ So one pass over the 81 cells is enough. Keep a “seen” set for each row, each column and each box. If a digit is already in any of the three, the board is invalid.
Edge cases to remember:
- Empty board (all '.') is valid.
- Don’t check solvability. Only check for duplicates.
- A box duplicate can sit in different rows and different columns (Example 2: (0,0) and (2,2)), so row and column checks alone don’t catch it.
- Check all 9 boxes, not just the diagonal ones (my second attempt checked only (0,0), (3,3), (6,6)).

Solution

Approach A — my version (three passes, join + `len(set)`)

Complexity: Time $O(81)$ (= $O(n^2)$ for an $n \times n$ board) · Space $O(9)$ per group. Correct, and the Big-O is the same as the best answer. It’s “not ideal” because:

Three separate passes over the board (rows, columns, boxes), with three copies of the same “join → strip dots → compare len to len(set)” logic.
No early exit inside a group: it builds the whole row/column/box string and the whole set before checking, instead of stopping at the first repeated digit.
The box loop is the fragile part: four nested loops with two offset variables (i, l). This is where both of my bugs were.
The string "".join(...).replace(".", "") trick works only because every cell is a single character.

The code is unchanged except for the signature and comments.

def is_valid_sudoku_mine(board: list[list[str]]) -> bool:
    for row in board:                                       # pass 1: rows
        nums = "".join(row).replace(".", "")
        if len(nums) != len(set(nums)):                     # builds the whole set, no early exit
            return False
    for col in range(9):                                    # pass 2: columns
        nums = []
        for row in range(9):
            nums.append(board[row][col])
        nums_str = "".join(nums).replace(".", "")
        if len(nums_str) != len(set(nums_str)):
            return False
    for i in range(0, 9, 3):                                # pass 3: boxes, 4 nested loops
        for l in range(0, 9, 3):
            nums = []

            for j in range(i, i + 3):
                for k in range(l, l + 3):
                    nums.append(board[j][k])
            nums_str = "".join(nums).replace(".", "")
            if len(nums_str) != len(set(nums_str)):
                return False

    return True

Approach B — one pass, a set per row / column / box ✅ best practice (interview answer)

Complexity: Time $O(81)$ · Space $O(81)$ (27 sets, at most 9 digits each). Walk every cell once. Skip '.'. Compute box = (r // 3) * 3 + c // 3. If the digit is already in rows[r], cols[c] or boxes[box], return False. Otherwise add it to all three. It stops at the first duplicate, has a single loop, and the box formula replaces the four nested loops.

def is_valid_sudoku(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):
            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

Approach C — one set of tagged tuples (Pythonic)

Complexity: Time $O(81)$ · Space $O(81)$ . Same idea, but all 27 groups share one set. Each digit is recorded three times as a tagged tuple: (r, d) for its row, (d, c) for its column (digit first, so it can’t collide with a row entry), and (r // 3, c // 3, d) for its box (length 3, so it can’t collide with either). Short and neat. In an interview, explain the tagging or use explicit tags like ("row", r, d).

def is_valid_sudoku_tuples(board: list[list[str]]) -> bool:
    seen = set()
    for r in range(9):
        for c in range(9):
            d = board[r][c]
            if d == ".":
                continue
            keys = ((r, d), (d, c), (r // 3, c // 3, d))
            if any(k in seen for k in keys):
                return False
            seen.update(keys)
    return True

Approach D — bitmasks

Complexity: Time $O(81)$ · Space $O(27)$ ints. Replace each set with a 9-bit integer: bit d is set once digit d has been seen. Checking and adding are one & and one |. This is the standard trick in C++/Java (and the base of Sudoku solvers, #37). In Python it isn’t faster, because of the int(d) and shift on every cell.

def is_valid_sudoku_bitmask(board: list[list[str]]) -> bool:
    rows = [0] * 9
    cols = [0] * 9
    boxes = [0] * 9
    for r in range(9):
        for c in range(9):
            d = board[r][c]
            if d == ".":
                continue
            bit = 1 << int(d)
            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

Scratch / Experiments

The board is always $9 \times 9$ , so Big-O is $O(1)$ for all of them and only constant factors matter. Worst case = a full valid board (no early exit, every cell is a digit). Also an empty board (all '.'), where the one-pass versions do almost nothing per cell.

Typical results (µs):

Approach	full valid	empty
A mine (3 passes, join + set)	~14	~12
B set per group ✅	~15.5	~4
C tagged tuples	~34	~2.7
D bitmask	~17	~2.6

Big-O and timing disagree here, and it’s worth knowing why:

A keeps up on a full board (and is slightly ahead) because most of its work is "".join, str.replace and set(str). Those are C-level loops over 9 characters, while B/C/D run Python bytecode for every one of the 81 cells (index, compare, 3 lookups, 3 adds).
On an empty / sparse board the one-pass versions are 3–4× faster: they just skip '.', while A still builds 27 strings and sets no matter what.
C is slowest on a full board: it builds 3 tuples per cell and hashes them, plus a generator in any. On an empty board it wins because it allocates only one set instead of 27.
D isn’t faster than B in Python: int(d) and 1 << ... cost about as much as a set lookup. Bitmasks pay off in C++/Java, not CPython.

So A isn’t “slow”. It’s verbose and fragile. B is the one to remember because it’s a single, general pass that’s easy to get right, early-exits, and scales to “check any grid constraint”.

FULL = [row[:] for row in SOLVED]
EMPTY = make_board({})

for label, board in [("full valid", FULL), ("empty", EMPTY)]:
    print(f"--- {label}")
    for fn in APPROACHES:
        print(f"{fn.__name__:28s}", end=" ")
        %timeit fn(board)

Takeaways

Pattern: “no duplicates within each group” → a seen set per group, filled in a single pass. For grids, map each cell straight to its groups: row r, column c, box (r // 3) * 3 + c // 3 (in general, block (r // h, c // w)). Computing the group index from the cell is simpler than looping over each group separately.
Mistakes I made:
- len(nums) != set(nums): compared an int to a set, which is always unequal, so it returned False on the first row. Compare len to len(set(...)).
- nums_str vs num_str: a typo that becomes a NameError.
- Box loop v1 used one index for both the row start and the column start, so it only checked the 3 diagonal boxes. Box loop v2 never offset j/k, so it checked the top-left box 3 times. Lesson: the 9 boxes need two independent starting coordinates, or no box loop at all if you use r // 3, c // 3.
- Tested only on the given examples, which both put the problem in the top-left box. Add a case for an off-diagonal box.
Related problems: Sudoku Solver (#37, same row/column/box sets plus backtracking; bitmasks are standard there), Contains Duplicate (#217, the single-group version of this), Set Matrix Zeroes (#73, per-row / per-column marking), N-Queens (#51, the same “which groups does this cell belong to” trick with diagonals r - c and r + c), Valid Anagram (#242, comparing counts instead of seen sets).