Valid Sudoku - Video Solutions

Problem Overview: You are given a partially filled 9x9 Sudoku board. The task is to determine whether the board configuration is valid. A valid board means each row, each column, and each 3x3 subgrid contains digits 1–9 without duplicates. Empty cells are represented by . and should be ignored during validation.

Approach 1: Hash Set Validation (Time: O(n^2), Space: O(n^2))

This approach tracks numbers seen in each row, column, and 3x3 box using hash sets. Iterate through the board cell by cell. When you encounter a digit, check whether it already exists in the corresponding row set, column set, or box set. If it does, the board is invalid. Otherwise insert the value into all three sets and continue scanning.

The key insight is treating rows, columns, and subgrids as independent constraints. A simple hash lookup (O(1)) detects duplicates immediately. You can compute the box index using (row / 3) * 3 + col / 3. This approach is straightforward and widely used in interview solutions involving hash tables and grid traversal problems built on arrays and matrix structures.

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

Bit manipulation compresses the same validation logic into integer bitmasks. Instead of hash sets, maintain three arrays: rows[9], cols[9], and boxes[9]. Each integer acts as a 9-bit mask representing digits 1–9. When processing a digit d, compute mask = 1 << (d - 1). If the mask already exists in the corresponding row, column, or box using a bitwise AND check, a duplicate was found.

If the digit is new, update the masks using bitwise OR. This technique eliminates dynamic data structures and reduces memory overhead while keeping constant-time checks. Bitmasking is common in constraint validation problems where the value range is small and fixed.

Recommended for interviews: The hash set solution is the most common answer and clearly communicates the validation logic. Interviewers expect you to recognize that rows, columns, and boxes must be tracked separately. The bit manipulation version demonstrates stronger optimization skills and understanding of low-level operations. Both run in O(n^2) time for a 9×9 board, but the bitmask approach achieves O(1) auxiliary space.