How to Explain Valid Sudoku in a Coding Interview (Step-by-Step)
Valid Sudoku isn’t about solving sudoku — it’s about validating it. The logic is straightforward, but most candidates struggle to articulate the box index formula cleanly. Nail that one piece and the rest falls into place.
In this post, you’ll learn exactly how to walk an interviewer through the Valid Sudoku problem: the three rules, the single-pass HashSet approach, and the box indexing trick that everyone trips over.
Problem Statement
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
1. Each row must contain digits 1–9 with no repetition.
2. Each column must contain digits 1–9 with no repetition.
3. Each of the nine 3×3 sub-boxes must contain digits 1–9 with no repetition.
Note: A valid board does not need to be solvable. Empty cells are represented by '.'.
Example Board
[“6″,”.”,”.”,”1″,”9″,”5″,”.”,”.”,”.”],
[“.”,”9″,”8″,”.”,”.”,”.”,”.”,”6″,”.”],
[“8″,”.”,”.”,”.”,”6″,”.”,”.”,”.”,”3″],
[“4″,”.”,”.”,”8″,”.”,”3″,”.”,”.”,”1″],
[“7″,”.”,”.”,”.”,”2″,”.”,”.”,”.”,”6″],
[“.”,”6″,”.”,”.”,”.”,”.”,”2″,”8″,”.”],
[“.”,”.”,”.”,”4″,”1″,”9″,”.”,”.”,”5″],
[“.”,”.”,”.”,”.”,”8″,”.”,”.”,”7″,”9″]
Constraints
board.length == 9board[i].length == 9board[i][j]is a digit1–9or'.'
What Is the Problem?
“I need to check whether the currently filled cells in a 9×9 board follow three rules — no duplicate in any row, no duplicate in any column, and no duplicate in any 3×3 box. Empty cells are ignored. I don’t need to solve the board, just validate what’s already filled.”
Emphasising “I don’t need to solve it” shows you’ve read the problem carefully — many candidates over-engineer this.
The Three Rules to Validate
The Key Insight — One Pass, Three HashSets
Instead of three separate passes (one per rule), do it all in a single pass. For each cell, check its digit against three HashSets simultaneously — one for its row, one for its column, and one for its 3×3 box. If any check fails, return false.
“I use three dictionaries of sets —rows,cols, andboxes. Each key is an index (0–8). For every filled cell(r, c), I check all three sets before adding to them. If the digit already exists in any one of them, the board is invalid.”
Step 2: Explain the Algorithm in Plain English
“I iterate over every cell in the 9×9 grid. If the cell is a dot I skip it. Otherwise I compute the box index for that cell, then check whether the digit already exists in its row set, column set, or box set. If it does — return false. If not — add it to all three and continue. If I finish without conflict — return true.”
The Box Index Trick — Most Candidates Struggle Here
The trickiest part is computing which of the 9 boxes a cell belongs to. The formula is:
box_index = (row // 3) * 3 + (col // 3)
Here’s why it works — row // 3 gives the box row (0, 1, or 2), and col // 3 gives the box column (0, 1, or 2). Multiplying the box row by 3 and adding the box column gives a unique index 0–8:
Being able to derive and explain this formula on the spot is what separates candidates who truly understand the problem from those who memorised the solution.
Step 3: Talk Through the Code
from collections import defaultdict
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
rows = defaultdict(set) # rows[r] = set of digits seen in row r
cols = defaultdict(set) # cols[c] = set of digits seen in col c
boxes = defaultdict(set) # boxes[b] = set of digits seen in box b
for r in range(9):
for c in range(9):
val = board[r][c]
if val == ".":
continue # Skip empty cells
box = (r // 3) * 3 + (c // 3) # Compute box index 0–8
# Check all three constraints simultaneously
if val in rows[r] or val in cols[c] or val in boxes[box]:
return False # Duplicate found — board is invalid
# No conflict — record this digit in all three structures
rows[r].add(val)
cols[c].add(val)
boxes[box].add(val)
return True # All cells passed — board is validPoint out the use of defaultdict(set) — it auto-creates an empty set for any new key, keeping the code clean without manual initialisation.
Step 4: Highlight Edge Cases
“A board of all dots is technically valid — there are no conflicts. Every cell is skipped, the loop finishes, we return true.”
“A digit appearing twice in the same row always fails the row check — even if they’re in different 3×3 boxes. The three checks are independent and all must pass.”
“It’s possible for all rows and columns to be valid while a 3×3 box has a duplicate. This is exactly why we need the box check as a separate constraint — rows and columns alone are not sufficient.”
“A board can pass all three rules and still be unsolvable — we don’t care. We’re only checking the current state of filled cells, not whether a valid completion exists.”
Step 5: State Time and Space Complexity
| Dimension | Complexity | Reason |
|---|---|---|
| Time | O(1) | Always exactly 81 cells — fixed input size |
| Space | O(1) | At most 81 entries across all sets — fixed upper bound |
“Since the board is always 9×9, both time and space are technically O(1) — constant. In practice it’s 81 cell operations and at most 81 set entries. If the interviewer asks about the general n×n case, time and space would both be O(n²).”
Interview Checklist for Valid Sudoku
- Restate — “validate filled cells against three rules, don’t solve the board”
- Name all three rules explicitly — row, column, 3×3 box
- State the key insight — single pass with three simultaneous HashSet checks
- Derive the box index formula —
(r // 3) * 3 + (c // 3)— and explain why it works - Use
defaultdict(set)and explain the convenience - Call out: rows + columns valid but box invalid is possible
- Call out: board doesn’t need to be solvable
- State O(1) time and space — fixed 9×9 board
- Mention O(n²) for the general n×n case if asked
- Ask before coding, don’t just dive in
Related Problems to Practice
If you can solve Valid Sudoku cleanly, try these next: