Valid Sudoku LeetCode 36 — HashSet Guide

LeetCode 36 Valid Sudoku asks you to determine whether a partially filled 9x9 Sudoku board is valid. The board contains digit characters from 1 through 9 and the character . for empty cells. Only the filled cells need to be validated — you do not need to check whether the board is solvable, only whether the existing digits obey the Sudoku rules.

The three Sudoku rules are: each row must contain the digits 1-9 with no repetition, each column must contain the digits 1-9 with no repetition, and each of the nine 3x3 sub-boxes of the grid must contain the digits 1-9 with no repetition. A board is valid if and only if none of these three constraints are violated by the filled cells.

This is a medium-difficulty problem that tests your ability to efficiently encode multiple constraints and check them simultaneously. The board is always exactly 9x9, which means the time and space complexity is technically O(1) — bounded by the fixed board size of 81 cells.

The straightforward approach iterates the board three separate times. First pass: for each of the 9 rows, collect all non-empty digits into a list and check for duplicates using a set. If any row has a repeated digit, return false. Second pass: iterate columns similarly — for each column index j, collect board[i][j] for all i from 0 to 8 and check for duplicates.

Third pass: for the 3x3 boxes, iterate over each box starting position at (box_row * 3, box_col * 3) for box_row and box_col in range(3). Collect all nine cells in the box and check for duplicates. If all three passes complete without finding duplicates, return true.

This three-pass approach works correctly and is O(81) = O(1) time since the board is fixed size. However, all three checks can be combined into a single pass over the board. One iteration, three constraints checked per cell — cleaner code, identical complexity, and easier to reason about.

The single-pass approach uses one set and checks all three constraints simultaneously for each cell. Iterate over every cell (i, j) from (0,0) to (8,8). Skip empty cells where board[i][j] == '.'. For each filled cell with digit d, compute three tuple keys: one encoding the row constraint, one for the column, and one for the box.

Before adding the keys to the set, check if any of the three already exists. If any key is already present, it means a duplicate was found in that row, column, or box — return false immediately. If none of the three keys exist in the set, add all three and continue to the next cell.

After processing all 81 cells with no conflicts found, return true. The single set holds at most 3 * 81 = 243 entries, all of which are constant-size tuples. The entire algorithm is O(1) time and O(1) space due to the fixed board dimensions.

The trickiest part of Valid Sudoku is correctly identifying which 3x3 box a cell belongs to. The formula is simple: box_row = i // 3 and box_col = j // 3, where // is integer division. These two values together uniquely identify one of the nine 3x3 boxes. The box key ("box", i//3, j//3, d) encodes both the box location and the digit.

For row index i: rows 0, 1, 2 all map to box_row 0 via integer division. Rows 3, 4, 5 map to box_row 1. Rows 6, 7, 8 map to box_row 2. The same logic applies to column index j for box_col. This creates a natural partitioning of the 9x9 grid into nine non-overlapping 3x3 blocks.

The nine resulting (box_row, box_col) pairs are (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2). Each pair identifies one 3x3 sub-box. The top-left box is (0,0) covering rows 0-2 and columns 0-2. The bottom-right box is (2,2) covering rows 6-8 and columns 6-8.

Instead of encoding constraints as tuple keys in one shared set, you can use three arrays of sets — one array of 9 sets for rows, one for columns, and one for boxes. rows[i] tracks digits seen in row i, cols[j] tracks digits in column j, and boxes[box_row * 3 + box_col] tracks digits in each 3x3 box using a flat array of 9 sets.

For each non-empty cell (i, j) with digit d: check if d is in rows[i], cols[j], or boxes[i//3 * 3 + j//3]. If any check is true, return false. Otherwise add d to all three sets. This approach uses 27 sets total, each holding at most 9 digits — still O(1) space for the fixed board size.

The separate-sets approach may feel clearer for some readers because each constraint is explicit and independent. The tuple-key approach uses one data structure but encodes the constraint type inside the key. Both approaches are O(81) = O(1) time and O(1) space. Pick whichever reads more naturally to you in an interview setting.

In Python, the tuple-key solution is around 10 lines. Initialize seen = set(). Loop over i in range(9) and j in range(9). Skip if board[i][j] == '.'. Assign d = board[i][j]. Check if any of ('row', i, d), ('col', j, d), ('box', i//3, j//3, d) is already in seen — if so, return False. Otherwise call seen.update([('row', i, d), ('col', j, d), ('box', i//3, j//3, d)]). Return True after the loops.

In Java, use a HashSet<String> and encode keys as strings like "row" + i + d, "col" + j + d, and "box" + (i/3) + (j/3) + d. Integer division in Java is automatic for int types, so i/3 gives the box row. For each cell, if !seen.add(key) returns false for any of the three keys, return false — the add method returns false when the element already exists, making the check concise.

Both solutions run in O(1) time and O(1) space since the board is always 9x9. There are exactly 81 iterations, and each iteration does constant work (three set lookups and three set insertions). The set holds at most 243 entries — 3 keys per cell times 81 cells — which is bounded by the fixed board size.

Valid Sudoku belongs to the matrix traversal and validation family. Its closest relative is Sudoku Solver (LeetCode 37), which uses backtracking to fill in the empty cells — building directly on the validation logic from LeetCode 36. Understanding Valid Sudoku is a prerequisite for implementing the solver efficiently.

Rotate Image (LeetCode 48) and Spiral Matrix (LeetCode 54) are also 2D matrix problems that require careful index arithmetic. Both test your comfort with nested loops over a 2D grid, but with transformation goals rather than validation. The box index formula i//3 and j//3 is a simpler relative of the rotation and spiral index mappings.

For set-based problems, Insert Delete GetRandom O(1) (LeetCode 380) exercises HashSet operations in a different context — building a data structure rather than validating a board. The hash set technique from Valid Sudoku recurs across many LeetCode problems: Two Sum, Contains Duplicate, and Longest Consecutive Sequence all rely on the same O(1) lookup property that makes the single-pass Sudoku solution elegant.