← Back to DSA Animator
Valid Sudoku LC #36 Medium Hash Sets
Problem

Determine if a 9×9 Sudoku board is valid. Only filled cells need to be validated: each row, each column, and each of the nine 3×3 boxes must contain the digits 1–9 without repetition. Empty cells are marked '.'.

Example 1
Input: board = (classic valid Sudoku board)
Output: true
Explanation: No duplicate digit in any row, column, or 3×3 box.
Example 2
Input: board = (board with '8' duplicated in column 0)
Output: false
Explanation: '8' appears in both row 0 and row 3 of column 0.
Constraints: board.length == 9  |  board[i].length == 9  |  board[i][j] is a digit '1'–'9' or '.'
Try Examples
Approach
One pass: for each non-empty cell, check row, column, and 3×3 box HashSets
Box index = (r/3)*3 + (c/3). If any duplicate found → invalid. O(1) space (fixed 9×9).
Sudoku Board
Row Status
Column Status
Box Status (row-major)
Variables
r (row)
—
c (col)
—
digit
—
row_valid
—
col_valid
—
box_valid
—
HashSet seen
empty
Step Logic
Press ▶ Play or Next Step to begin the animation.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Init 9 row sets, 9 col sets, 9 box sets (or one combined seen set)
2
For each cell: skip '.'. Compute box = (r/3)*3 + c/3
3
If digit already in row[r], col[c], or box[box] → return false
4
Otherwise add digit to all three sets and continue
5
If all 81 cells pass → return true
Time
O(81) = O(1)
Space
O(81) = O(1)
Why HashSets Work

The board is always exactly 9×9 with at most 81 cells, so both time and space are O(1) — bounded by a constant. Three families of sets (rows, columns, boxes) guarantee that each constraint unit is checked independently. The single-pass scan never backtracks: the moment a duplicate is found in any unit, we immediately return false.