LeetCode 36 – Valid Sudoku

Valid Sudoku has no algorithm in it at all — it is a bookkeeping problem. The instinct is three separate passes: one for rows, one for columns, one for the 3×3 boxes. All three can be done in a single pass over the grid, and the only genuinely interesting line in the whole solution is the formula that maps a cell to its box.

The problem

Decide whether a partially filled 9×9 Sudoku board is valid: no digit repeats within any row, any column, or any 3×3 box. Empty cells are '.' and are not checked.

The board only has to be valid, not solvable. Those are different questions, and this one is much easier — you are checking the rules as they stand, not whether the puzzle can be finished.

The box index

Rows and columns are trivial; the boxes are where people write four nested loops. They do not need to. Integer division collapses each coordinate to which band of three it falls in, and the two bands combine into a box number from 0 to 8:

box = (row / 3) * 3 + col / 3

     col: 012 345 678
row 0-2:   0   1   2
row 3-5:   3   4   5
row 6-8:   6   7   8

(0,0) and (2,2) -> box 0        (4,7) -> (4/3)*3 + 7/3 = 3 + 2 = 5

Row 4 divided by 3 is 1, times 3 is 3 — that skips a whole band of three boxes. Column 7 divided by 3 is 2, the offset within the band. The formula is worth deriving out loud rather than recalling; it is the same trick that flattens any 2-D grid to 1-D, and interviewers ask for it in several other problems.

One pass, one set

With the box number in hand, every cell contributes exactly three facts: this digit is in this row, this digit is in this column, this digit is in this box. Record all three as distinct keys in one set. If any key is already present, the board is invalid.

Encoding the three into one set rather than keeping 27 separate sets is what shrinks the solution to a dozen lines. The keys must be unambiguous — "5" + "0" would be the same string for "5 in row 0" and "5 in column 0" without a discriminator — so include which kind of constraint it is.

Java

class Solution {
    public boolean isValidSudoku(char[][] board) {
        Set<String> seen = new HashSet<>();

        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                char digit = board[row][col];
                if (digit == '.') continue;         // empty cells are not checked

                int box = (row / 3) * 3 + col / 3;

                // add() returns false when the key was already present.
                if (!seen.add(digit + " in row " + row)
                        || !seen.add(digit + " in col " + col)
                        || !seen.add(digit + " in box " + box)) {
                    return false;
                }
            }
        }

        return true;
    }
}

Set.add returning false on a duplicate is what makes this read as one condition rather than a check followed by an insert. The || short-circuits, so a later add is skipped once one has already failed — harmless, since the method returns immediately.

Python

class Solution:
    def isValidSudoku(self, board: list[list[str]]) -> bool:
        seen = set()

        for row in range(9):
            for col in range(9):
                digit = board[row][col]
                if digit == ".":
                    continue

                box = (row // 3) * 3 + col // 3
                keys = ((digit, "row", row), (digit, "col", col), (digit, "box", box))

                if any(key in seen for key in keys):
                    return False
                seen.update(keys)

        return True

Tuples make better keys than concatenated strings — no separator to get wrong, no chance of two different facts colliding, and no string building in the inner loop.

The bitmask version

If asked to avoid the hashing, nine digits fit in nine bits, so each row, column and box can be a single int. This is what you would write if the check sat in a solver's hot loop:

int[] rows = new int[9], cols = new int[9], boxes = new int[9];

for (int row = 0; row < 9; row++) {
    for (int col = 0; col < 9; col++) {
        if (board[row][col] == '.') continue;

        int bit = 1 << (board[row][col] - '1');   // '1'..'9' -> bits 0..8
        int box = (row / 3) * 3 + col / 3;

        if ((rows[row] & bit) != 0 || (cols[col] & bit) != 0 || (boxes[box] & bit) != 0) {
            return false;
        }
        rows[row] |= bit;
        cols[col] |= bit;
        boxes[box] |= bit;
    }
}
return true;

Same complexity, no allocation, no hashing, and 27 integers of state instead of a set holding up to 243 keys. Offer it as the follow-up rather than opening with it — the set version is clearer and clarity comes first.

Complexity

O(1) for both, and say it that way. The board is fixed at 9×9, so this is 81 cells and at most 243 insertions no matter what. If pressed for the general n²×n² case it is O(n⁴) cells with O(n⁴) space — but stating O(1) first shows you noticed the size is a constant, which is the point.

What the interviewer is checking

• The box index formula, and whether you can derive it rather than recall it.
• That you do it in one pass instead of three.
• That '.' is skipped — treating it as a value makes any board with two blanks invalid.
• That the encoded keys cannot collide between the three constraint types.
• That you know valid is not the same as solvable, and do not start writing a solver.
• Whether you can produce the bitmask version when asked to drop the hashing.