36. Valid Sudoku

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 the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. Each of the nine 3 x 3 sub-boxes must contain the digits 1-9 without repetition.

Note: We are NOT solving Sudoku. Just validating the current board. Empty cells are represented by '.'.

Examples

Example 1:

Input: board =
[["5","3",".",".","7",".",".",".","."]
,["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"]]
Output: true

Example 2:

Input: board = (same as above but with board[0][0] changed to "8")
Output: false
Explanation: Two 8's in the top-left 3x3 sub-box.

Constraints

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit 1-9 or '.'

Clarification Questions

  1. Validate only: We are not solving, only checking validity? (Assumption: Yes.)
  2. Empty cells: ‘.’ ignored for duplicate check? (Assumption: Yes.)
  3. Board size: Always 9×9? (Assumption: Yes.)
  4. Sub-boxes: Nine 3×3 boxes as in standard Sudoku? (Assumption: Yes.)
  5. Partial fill: Some cells can be empty? (Assumption: Yes.)

Interview Deduction Process (20 minutes)

Step 1: Three passes (5 min) — Check 9 rows, then 9 columns, then 9 sub-boxes for duplicate digits. Use a set per group. O(1) since 81 cells.

Step 2: Single pass with 27 sets (7 min) — For each cell (i, j) with digit d, check row i, col j, and box (i//3, j//3). If d already in any of those sets, return false; else add d to all three. O(1).

Step 3: Bitmask (8 min) — Same logic but use one int per row/col/box: set bit (d-1). Check with (mask » (d-1)) & 1; set with mask = (1 « (d-1)). Clean and fast.

Solution Approach

Fixed size 9x9 – maximum 81 cells, so time complexity is essentially constant. This problem is not about performance; it’s about clean constraint modeling.

We need to detect duplicates across 27 constraint groups:

  • 9 rows
  • 9 columns
  • 9 sub-boxes (3x3 blocks)

Why Bitmask?

Instead of using set or unordered_set, use an integer bitmask per group:

  • Faster – no hash overhead
  • Cleaner – single integer per group
  • Classic bit manipulation trick

Encoding

For digit d (character '1' to '9'):

num = d - '1'       // 0..8
mask = 1 << num     // one-hot bit

Each row/col/box maintains an integer. If the bit is already set, we found a duplicate.

Box Index: Why (i/3)*3 + (j/3) Works

The 9 sub-boxes are indexed as:

0 1 2
3 4 5
6 7 8
  • (i / 3) gives the block row (0, 1, or 2)
  • (j / 3) gives the block column (0, 1, or 2)
  • Combined: (i / 3) * 3 + (j / 3) maps to 0..8

Common wrong formula: (i % 3) * 3 + (j % 3) – this gives position within a box, not the box index.

Approach

Single pass over all 81 cells. For each filled cell:

  1. Compute num = board[i][j] - '1' and mask = 1 << num
  2. Compute boxIndex = (i / 3) * 3 + (j / 3)
  3. Check if mask already exists in row[i], col[j], or box[boxIndex]
  4. If yes, return false. Otherwise, set the bit.

Time Complexity: $O(81)$ = $O(1)$ Space Complexity: $O(1)$ (27 integers)

Solution

class Solution:
def isValidSudoku(self, board):
    row[9] = :0
col[9] = :0
box[9] = :0
for (i = 0 i < 9 i += 1) :
for (j = 0 j < 9 j += 1) :
if (board[i][j] == '.') continue
num = board[i][j] - '1'   // 0..8
mask = 1 << num
boxIndex = (i / 3)  3 + (j / 3)
if (row[i] * mask) return False
if (col[j] * mask) return False
if (box[boxIndex] * mask) return False
row[i] |= mask
col[j] |= mask
box[boxIndex] |= mask
return True

Common Mistakes

  • Using unordered_set inside loops – slower and messier than bitmask
  • Forgetting to skip '.' cells
  • Wrong box index formula ((i % 3) * 3 + (j % 3) is position within a box, not the box index)

Key Takeaways

This problem tests:

  • Constraint modeling – 27 groups validated in one pass
  • Bitmask usage – one integer per constraint group
  • Grid indexing mapping – the (i/3)*3 + (j/3) trick
  • Clean $O(1)$ structure design – no containers, just arrays

Template Reference