Valid Sudoku - Solution & Explanation

Problem Overview: Given a partially filled 9x9 Sudoku board, determine whether it follows Sudoku rules. Each row, column, and 3x3 sub-box must contain digits 1–9 without duplicates. Empty cells are represented by . and should be ignored during validation.

Approach 1: Hash Set Validation (Time: O(81), Space: O(81))

The most straightforward method scans the board once while tracking seen numbers for rows, columns, and 3x3 boxes using hash sets. For each cell, skip .. Otherwise check whether the number already exists in the corresponding row set, column set, or box set. If any lookup returns true, the board is invalid. Otherwise insert the number into all three structures.

This works because hash table lookups run in O(1) average time. You typically maintain three collections: rows[9], cols[9], and boxes[9]. The box index is computed using (r / 3) * 3 + (c / 3). Since the board size is fixed (9×9), the algorithm processes at most 81 cells, giving O(81) time and O(81) auxiliary space. This approach is easy to implement and commonly used in interviews when working with arrays and grid-style problems.

Approach 2: Bit Manipulation (Time: O(81), Space: O(1))

Bit manipulation compresses the same validation logic into integer bitmasks. Instead of hash sets, use three arrays of integers to represent rows, columns, and boxes. Each digit 1–9 maps to a bit position. When reading a number, compute mask = 1 << digit and check whether that bit already exists in the corresponding row, column, or box mask using a bitwise AND.

If the bit is already set, the board violates Sudoku rules. Otherwise update the mask using a bitwise OR. This approach removes the overhead of hash structures and keeps memory constant. It still iterates through the board once, so the time complexity remains O(81), but the space complexity drops to O(1) since only fixed-size integers are used. Bitmask techniques are common when solving constraint problems on a matrix with small value ranges.

Recommended for interviews: Hash set validation is the expected solution for most interviews because it is easy to reason about and clearly expresses the constraint checks. Bit manipulation demonstrates deeper optimization and stronger low-level problem solving. Showing the hash-set approach first proves correctness, then mentioning the bitmask optimization signals strong algorithmic maturity.