# Valid Sudoku

[link](https://leetcode.com/problems/valid-sudoku/) · Medium · `array`, `hash set`, `matrix`

> "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.

## 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:
1. **Three separate passes** over the board (rows, columns, boxes), with three copies of the
   same "join → strip dots → compare `len` to `len(set)`" logic.
2. **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.
3. **The box loop is the fragile part:** four nested loops with two offset variables (`i`, `l`).
   This is where both of my bugs were.
4. The string `"".join(...).replace(".", "")` trick works only because every cell is a single
   character.

The code is unchanged except for the signature and comments.

```python
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.

```python
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)`.

```python
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.

```python
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".

```python
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).

---

From https://taosu.blog/notes/0036-valid-sudoku