Valid Sudoku

1. Problem & Core Objective

The problem

Determine whether a 9×9 Sudoku board is valid. Only the filled cells need to be checked, according to three rules:

1. Each row must contain the digits 1–9 without repetition.
2. Each column must contain the digits 1–9 without repetition.
3. Each of the nine 3×3 sub-boxes must contain the digits 1–9 without repetition.

Empty cells are represented by '.'.

Important: the board may be partially filled, and you are only validating what's there. A valid board is not necessarily solvable.

Constraints:

• board.length == 9, board[i].length == 9
• board[i][j] is a digit '1'–'9' or '.'

What the interviewer is actually testing

The algorithm is not hard. What's being assessed is bookkeeping discipline:

1. Can you track three independent constraint families at once without writing three separate loops?
2. Do you know the 3×3 box index formula? (r / 3) * 3 + c / 3 is the one piece of arithmetic here, and it's reusable well beyond Sudoku.
3. Do you read the problem carefully? Two traps: only filled cells count, and validity ≠ solvability. Candidates who skim try to solve the puzzle.
4. Can you avoid the naive 27-pass solution? Everything can be done in a single sweep.

The board is fixed at 9×9, so every complexity here is technically O(1). Saying that — and then giving the honest O(n²) in terms of board size — is the distinguishing move.

2. First-Principles Thought Process

Step 1 — Restate the rules mechanically

"No repetition within a group" means: as I encounter each digit, has this digit already appeared in this group?

That's a membership question, asked repeatedly — which is a HashSet (or, since digits are 1–9, a small fixed array or a bitmask).

Step 2 — Identify the groups

Every filled cell belongs to exactly three groups simultaneously:

• its row (9 of them),
• its column (9 of them),
• its 3×3 box (9 of them).

So a digit at (r, c) must be checked against, and recorded in, all three.

Step 3 — The naive structure, and why to avoid it

The obvious approach is three separate double-loops: one validating rows, one columns, one boxes. It works, but:

• Three passes over the board instead of one.
• Three near-identical blocks of code — more surface area for bugs.
• The box loop needs awkward nested indexing.

Better: one pass, three sets of trackers. At each cell, do all three checks.

Step 4 — The only real arithmetic: the box index

Rows and columns index themselves. Boxes need a mapping from (r, c) to a box number 0–8.

Integer division does it. Rows 0,1,2 all give r / 3 == 0; rows 3,4,5 give 1; rows 6,7,8 give 2:

Same for columns. So (r/3, c/3) identifies the box as a coordinate pair. To flatten it into a single index 0–8:

int box = (r / 3) * 3 + c / 3;

This is row-major flattening — the same row * width + col arithmetic used for 2-D-to-1-D conversion throughout (02 §8.5).

Box layout:

        c/3=0   c/3=1   c/3=2
r/3=0 |   0   |   1   |   2   |
r/3=1 |   3   |   4   |   5   |
r/3=2 |   6   |   7   |   8   |

Verify with a cell: (4, 7) → (4/3)*3 + 7/3 = 1*3 + 2 = 5. Row 4, column 7 is in the middle-right box. ✓

Step 5 — Choose the tracker

Three options, all correct:

• Set<String> with tagged keys — one set, keys like "5@row0". Fewest moving parts.
• Arrays of sets — Set<Character>[] rows, cols, boxes. Explicit but verbose in Java (generic array creation).
• boolean[9][9] or bitmasks — fastest, no hashing at all.

3. Solution Paths

Approach 1 — Three separate passes

public boolean isValidSudoku(char[][] board) {
    // rows
    for (int r = 0; r < 9; r++) {
        Set<Character> seen = new HashSet<>();
        for (int c = 0; c < 9; c++) {
            char v = board[r][c];
            if (v != '.' && !seen.add(v)) return false;
        }
    }
    // columns
    for (int c = 0; c < 9; c++) {
        Set<Character> seen = new HashSet<>();
        for (int r = 0; r < 9; r++) {
            char v = board[r][c];
            if (v != '.' && !seen.add(v)) return false;
        }
    }
    // boxes
    for (int b = 0; b < 9; b++) {
        Set<Character> seen = new HashSet<>();
        int startR = (b / 3) * 3, startC = (b % 3) * 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                char v = board[startR + i][startC + j];
                if (v != '.' && !seen.add(v)) return false;
            }
        }
    }
    return true;
}

Correct and readable. Note the box loop inverts the earlier formula: given box b, its top-left corner is ((b/3)*3, (b%3)*3).

• Time: O(1) — the board is fixed. In terms of side length n: O(n²).
• Space: O(1) — at most 9 characters in a set at a time. O(n) in general.

Three passes and three near-duplicate blocks. Fine as a first answer; the single-pass version is tidier.

Counter-questions on this approach

⭐ "Wait — am I checking whether the board is solvable, or just currently valid?"

Only currently valid. This is the trap in the question. A board can satisfy all three rules and still have no completion, and the answer is still true. I'm validating state, not solvability — worth confirming with the interviewer before writing anything.

"Three near-identical blocks. Any risk in that?"

Yes — copy-paste bugs, and specifically in the third block, where the indexing differs. It's also three passes over the board. Folding them into one pass keeps all three checks adjacent, so a reader can see at a glance that every rule is enforced at the same moment.

"Explain the indexing in your box loop — it's different from the formula you use elsewhere."

It's the inverse mapping. Elsewhere I go from a cell to its box: (r/3)*3 + c/3. Here I go from a box number b to its top-left corner: ((b/3)*3, (b%3)*3). Both directions are worth knowing; the second also appears in Sudoku solvers.

Approach 2 — One pass with tagged string keys

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

    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            char v = board[r][c];
            if (v == '.') continue;                       // only filled cells count

            int box = (r / 3) * 3 + c / 3;

            if (!seen.add(v + "@row" + r) ||
                !seen.add(v + "@col" + c) ||
                !seen.add(v + "@box" + box)) {
                return false;
            }
        }
    }
    return true;
}

How it works. One set holds every observation, with the group tagged into the key so the three families can't collide. A 5 in row 0 produces "5@row0"; a 5 in column 0 produces "5@col0" — different strings, no false conflict.

Set.add returns false when the element is already present, so a failed add is a duplicate detection. The short-circuiting || means the first failing check returns immediately.

Trace on a small conflict. Suppose board[0][0] = '5' and board[0][4] = '5' (same row):

• Time: O(1) (board fixed); O(n²) in side length.
• Space: O(1); up to 243 strings for a full board.

The cost: three string concatenations per cell, each allocating. Correct but not fast. Good for showing the idea clearly.

Counter-questions on this approach

⭐ "You're building three strings per cell. What does that cost?"

Each concatenation allocates a StringBuilder, converts an int to characters, and produces a String that then has to be hashed — three times for all 81 cells. It's the same big-O but roughly an order of magnitude slower than direct indexing. It's a good way to show the idea, not the version I'd ship.

"Why tag the keys at all — why not three separate sets?"

Three sets would work. Tagging lets me use one set by making the three constraint families occupy disjoint key spaces: "5@row0" and "5@col0" can't collide. Without a tag, a 5 in row 0 would falsely conflict with a 5 in column 0.

Approach 3 — Bitmasks (optimal)

public boolean isValidSudoku(char[][] board) {
    int[] rows  = new int[9];
    int[] cols  = new int[9];
    int[] boxes = new int[9];

    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            char v = board[r][c];
            if (v == '.') continue;

            int bit = 1 << (v - '1');               // digit '1'..'9' -> bit 0..8
            int box = (r / 3) * 3 + c / 3;

            if ((rows[r]  & bit) != 0) return false;    // already in this row
            if ((cols[c]  & bit) != 0) return false;    // already in this column
            if ((boxes[box] & bit) != 0) return false;  // already in this box

            rows[r]  |= bit;                        // record it
            cols[c]  |= bit;
            boxes[box] |= bit;
        }
    }
    return true;
}

How it works. Each int stores nine yes/no flags in its low nine bits. Bit d set means "digit d+1 has appeared in this group".

• 1 << (v - '1') turns digit '1' into bit 0, '2' into bit 1, …, '9' into bit 8.
• x & bit is non-zero exactly when that bit is already set — the membership test.
• x |= bit sets it — the insert.

Worked bit example. Say row 0 has already seen digits 3 and 7:

rows[0] = 0 1000 0100        (bit 2 for '3', bit 6 for '7')

Now a '3' arrives: bit = 1 << 2 = 0000 0100.

rows[0] & bit = 0 1000 0100
              & 0 0000 0100
              = 0 0000 0100   ≠ 0   →  duplicate, return false   ✓

• Time: O(1) (board fixed); O(n²) in side length.
• Space: O(1) — 27 ints, always.

Why this is the optimal version: no hashing, no allocation, no objects. Three array reads, three bitwise ANDs, three ORs per cell. See 22 — Bit Manipulation.

Counter-questions on this approach

⭐ "Walk me through the bit test on a concrete value."

Say row 0 has already seen 3 and 7, so rows[0] is 0b0_1000_0100 — bit 2 for the 3, bit 6 for the 7. A '3' arrives, giving bit = 1 << 2 = 0b100. The AND is 0b100, which is non-zero, so it's a duplicate and I return false. If the digit were new, the AND would be 0 and I'd set it with |=.

⭐ "Why bitmasks rather than a HashSet per group?"

The key space is nine digits — tiny, fixed, and known in advance. That's precisely when direct indexing beats hashing. A bitmask packs nine booleans into one int, making membership a single AND and insertion a single OR, with no allocation and no hashing. It's the same reasoning as int[26] in Valid Anagram, at a smaller scale.

"Why do you write (rows[r] & bit) != 0 instead of rows[r] & bit != 0?"

Because in Java & binds looser than ==. The unparenthesized version parses as rows[r] & (bit != 0), which is an int & boolean and doesn't compile. Bitwise comparisons always need the parentheses.

"What's your complexity, precisely?"

The board is fixed at 9×9, so strictly it's O(1) — 81 cells and 27 trackers, all constant. Generalized to an n²×n² board it's O(n⁴) time in n, which is linear in the number of cells, with O(n²) space. I'd state O(1) for this problem and flag that the general framing differs.

Approach 4 — Boolean arrays (the readable middle ground)

boolean[][] rows  = new boolean[9][9];
boolean[][] cols  = new boolean[9][9];
boolean[][] boxes = new boolean[9][9];

// ...
int d = v - '1';                                  // 0..8
int box = (r / 3) * 3 + c / 3;
if (rows[r][d] || cols[c][d] || boxes[box][d]) return false;
rows[r][d] = cols[c][d] = boxes[box][d] = true;

Nearly as fast as bitmasks and much easier to read. If you're unsure about bit syntax under pressure, write this — it loses almost nothing.

Counter-questions on this approach

⭐ "If bitmasks are faster, why would you ever write this?"

It's nearly as fast — an array read instead of a shift and an AND — and substantially easier to read and to get right. If I were unsure of the bit syntax under time pressure, this version loses almost nothing and eliminates a whole class of precedence and off-by-one errors. Knowing when not to use the clever version is part of the answer.

Comparison

4. Why the Optimal Wins

Against three passes. Same asymptotics, but one pass touches each cell once and keeps all three checks adjacent — so the reader (and you) can see that all three rules are enforced at the same moment. Three separate loops invite a copy-paste bug in the third.

Against tagged strings. Building v + "@row" + r allocates a StringBuilder, converts an int to characters, and produces a String that then gets hashed — three times per cell. Bitmasks replace all of that with a shift and an AND. Same big-O, roughly an order of magnitude apart in practice.

The conceptual point worth voicing:

"A HashSet is what you use when the key space is large or unknown. Here the key space is nine digits — tiny, fixed, and known in advance. So I can use direct indexing instead of hashing. A bitmask is the extreme version of that: nine booleans packed into one integer, with membership as a single AND."

That connects this problem to the int[26] in Valid Anagram — the same idea at a different scale.

On complexity — be precise, this is where candidates get sloppy:

"The board is fixed at 9×9, so strictly everything here is O(1) — 81 cells, 27 trackers, constant. If you generalize to n² cells with n symbols, it's O(n²) time and O(n) space with bitmasks. I'll state it as O(1) for this problem since the size is fixed."

Claiming O(n²) without acknowledging the board is fixed, or claiming O(1) without explaining why, both read as imprecise.

5. Java Prerequisites

The box index formula

int box = (r / 3) * 3 + c / 3;

Two steps: (r/3, c/3) gives the box's coordinate pair, and * 3 + flattens it row-major into 0–8.

The inverse — given box b, find its top-left corner:

int startR = (b / 3) * 3;
int startC = (b % 3) * 3;

Both directions are worth knowing; the second appears in the three-pass version and in Sudoku solvers.

Character-to-index arithmetic

int d = v - '1';              // '1'->0, '2'->1, ... '9'->8
int bit = 1 << (v - '1');     // '1'->bit 0, ... '9'->bit 8

Note '1' not '0' — Sudoku digits start at 1, so subtracting '1' gives a 0-based index directly.

Bitwise operators

(mask & bit) != 0        // is this bit set?  (membership test)
mask |= bit              // set the bit        (insert)
1 << k                   // a mask with only bit k set

Parenthesize the comparison. & binds looser than == in Java, so if (mask & bit != 0) parses as mask & (bit != 0) and fails to compile. Always write (mask & bit) != 0. See 22.

Set.add as a duplicate test

if (!seen.add(key)) return false;       // add returned false => already present

One operation instead of contains followed by add.

Generic array creation

Set<Character>[] rows = new Set[9];       // unchecked warning — generics + arrays don't mix

Java forbids new Set<Character>[9]. Use the raw form with a warning, or prefer boolean[9][9] / int[9], which avoid the issue entirely.

2-D array traversal

for (int r = 0; r < 9; r++)
    for (int c = 0; c < 9; c++)
        board[r][c];

board[r][c] is row r, column c. Transposing these by accident silently validates columns as rows — and on a symmetric test board it still passes.

6. Interview Communication Guide

Clarifying questions

1. "Do I need to check solvability, or only that the current state is valid?" — the single most important question. The answer is validity only, and asking proves you read carefully.
2. "Are empty cells always '.', or could there be spaces or nulls?"
3. "Is the board guaranteed 9×9 and well-formed?" — decides whether to write defensive checks.
4. "Could there be characters other than 1–9 and .?" — if so, v - '1' could index out of bounds.
5. "Should I mutate the board?" — not needed here, but good habit.

The pitch

"Three rules: no repeats within a row, a column, or a 3×3 box. Every filled cell belongs to exactly one of each, so I can validate all three in a single pass rather than three separate sweeps.

I'll keep three trackers — one per row, per column, per box. At each filled cell I check all three for the digit, and if any already has it, the board is invalid. Otherwise I record it in all three.

The only arithmetic is mapping a cell to its box. Integer division gives the block coordinates: (r/3, c/3). Flattening that row-major gives (r/3)*3 + c/3, a single index 0–8.

For the trackers, digits are only 1–9 — a tiny fixed key space. So instead of hash sets I'll use bitmasks: one int per group, with bit d meaning 'digit d+1 seen'. Membership is one AND, insertion is one OR.

The board is fixed at 9×9 so this is technically O(1) — 81 cells, 27 ints. Generalized to n×n it's O(n²) time, O(n) space.

One thing I want to confirm: I'm only checking the current state is valid, not that the puzzle is solvable — correct?"

Edge cases to raise proactively

The last two are the ones to volunteer. The box-only duplicate catches solutions that forgot the third rule. And the unsolvable-but-valid case proves you understood the question — a board can satisfy all three rules and still have no solution, and the answer is still true.

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. These are new problems, asked after your solution is accepted — not challenges to it. (Those are the counter-questions attached to each approach in §3.) ⭐ marks the most likely.

⭐ "Now actually solve the Sudoku."

Backtracking. Find an empty cell, try digits 1–9, keep the ones that don't violate the three masks, recurse, and undo the mask bits on the way out. The validity check you just wrote becomes the pruning step.

The key connection: the masks make each placement check O(1) instead of scanning 27 cells. That's the difference between a solver that finishes and one that doesn't. See 15 — Backtracking.

"Generalize to an n²×n² board with n×n boxes."

The box formula becomes (r/n)*n + c/n. Bitmasks work while n² <= 32 (or 64 with long); beyond that use boolean[] or BitSet. Time O(n⁴) in n, i.e. linear in the number of cells.

"What if the board is enormous and sparse?"

Store only filled cells as (row, col, digit) and use hash sets keyed by group — memory proportional to filled cells rather than board area.

"Can you validate in parallel?"

Yes — the three rule families are independent, so rows, columns, and boxes can be checked concurrently. Within a family, each of the nine groups is independent too. It's embarrassingly parallel; the only shared state is the early-exit flag.

"What if you had to report which cells conflict, not just true/false?"

Don't return early. Store the first position for each (group, digit) observation instead of a bit, so when a conflict appears you have both coordinates. Space goes from 27 ints to a map, but you get actionable output.