← ~/lc-grind/posts

#36 - Valid Sudoku

October 7, 2025

Valid Sudoku

Problem Description

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 of the grid must contain the digits 1-9 without repetition.

Note:

  • A Sudoku board (partially filled) could be valid but is not necessarily solvable.
  • Only the filled cells need to be validated according to the mentioned rules.

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 = 
[["8","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: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Constraints:

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

Solution

1. Problem Deconstruction (500+ words)

Technical Restatement
We must validate a 9×9 Sudoku board’s partial configuration against three combinatorial constraints:

  1. Row Invariant: ∀i ∈ [0,8], the set {board[i][j] | 0≤j≤8} ∩ ℤ must contain distinct digits 1-9
  2. Column Invariant: ∀j ∈ [0,8], the set {board[i][j] | 0≤i≤8} ∩ ℤ must contain distinct digits 1-9
  3. Sub-box Invariant: For all (r,c) ∈ {0,1,2}², the set {board[3r+δ₁][3c+δ₂] | δ₁,δ₂ ∈ [0,2]} ∩ ℤ must contain distinct digits 1-9

Beginner-Friendly Version
Imagine a 9×9 grid partially filled with numbers 1-9. We need to check if:

  • No row has duplicate numbers
  • No column has duplicate numbers
  • No 3×3 block (there are 9 of them) has duplicate numbers Empty cells (marked ‘.’) don’t affect these rules.

Mathematical Formulation
Let B[i][j] ∈ {1,…,9,‘.’} be the board elements. Define:

  • R(i) = {B[i][j] | 0≤j≤8} \ {‘.’}
  • C(j) = {B[i][j] | 0≤i≤8} \ {‘.’}
  • B(k) = {B[3⌊k/3⌋+δ₁][3(k mod 3)+δ₂] | δ₁,δ₂ ∈ [0,2]} \ {‘.’}

The board is valid iff ∀i,j,k: |R(i)| = |set(R(i))| ∧ |C(j)| = |set(C(j))| ∧ |B(k)| = |set(B(k))|

Constraint Analysis

  • board.length == 9, board[i].length == 9: Fixed size enables O(1) space solutions
  • board[i][j] is digit 1-9 or '.': No invalid characters simplifies validation
  • Hidden edge cases: All empty boards are valid; duplicate digits in any dimension invalidate; single filled cell boards are trivially valid

2. Intuition Scaffolding

Real-World Metaphor
Like organizing a 9-floor apartment building where each floor (row) must have unique apartment numbers, each elevator shaft (column) must serve unique numbers, and each 3×3 wing section must contain unique numbers.

Gaming Analogy
Similar to checking if a partially filled Magic Square follows its rules before attempting completion - we verify local constraints without solving the global puzzle.

Math Analogy
Validating three orthogonal Latin squares simultaneously - rows, columns, and blocks each form partial permutations.

Common Pitfalls

  1. Checking only filled cells but missing empty cell handling
  2. Forgetting that ‘.’ doesn’t count as duplicates
  3. Incorrect sub-box indexing (0-8 vs 1-9 confusion)
  4. Using O(n²) space for constant-size problem
  5. Validating solvability instead of just configuration validity

3. Approach Encyclopedia

Brute Force (Triple Validation)

For each row i (0-8):
    seen = set()
    For each cell in row:
        if cell != '.' and cell in seen: return false
        else add to seen

Repeat for columns
Repeat for 3×3 blocks

Time: 9 rows × 9 checks + 9 cols × 9 checks + 9 blocks × 9 checks = 243 = O(1)
Space: O(1) temporary sets

Optimized (Single Pass with Encoded Sets)

rows = [0]*9, cols = [0]*9, boxes = [0]*9
For i in 0..8:
    For j in 0..8:
        if board[i][j] == '.': continue
        num = int(board[i][j])
        bitmask = 1 << (num-1)
        
        # Check row i
        if rows[i] & bitmask: return false
        rows[i] |= bitmask
        
        # Check column j  
        if cols[j] & bitmask: return false
        cols[j] |= bitmask
        
        # Check box k = 3*(i//3) + (j//3)
        k = 3*(i//3) + j//3
        if boxes[k] & bitmask: return false
        boxes[k] |= bitmask

Time: 81 iterations = O(1)
Space: 27 integers = O(1)

Visualization

Row Check:      Column Check:    Box Check:
[5 3 . 7 . .]  [5 6 . 8 4 7]   [5 3 .][6 . .][. 9 8]
                                      ↖ Box (0,0)

4. Code Deep Dive

def isValidSudoku(board):
    # Track seen digits using bitmasking (9 bits per dimension)
    rows = [0] * 9  # Each integer tracks 9 digits for a row
    cols = [0] * 9  # Each integer tracks 9 digits for a column  
    boxes = [0] * 9 # Each integer tracks 9 digits for a 3×3 box
    
    for i in range(9):
        for j in range(9):
            if board[i][j] == '.':
                continue  # Skip empty cells
                
            # Convert char to int and create bitmask
            num = int(board[i][j])  # '5' → 5
            bit = 1 << (num - 1)    # 5 → 1<<4 = 16 (000010000)
            
            # Check row constraint
            if rows[i] & bit:  # Bit already set in this row
                return False
            rows[i] |= bit     # Mark digit as seen in row
            
            # Check column constraint  
            if cols[j] & bit:  # Bit already set in this column
                return False
            cols[j] |= bit     # Mark digit as seen in column
            
            # Calculate box index and check box constraint
            box_idx = 3 * (i // 3) + j // 3  # Maps (i,j) to box 0-8
            if boxes[box_idx] & bit:  # Bit already set in this box
                return False
            boxes[box_idx] |= bit     # Mark digit as seen in box
            
    return True  # All constraints satisfied

Edge Case Handling

  • Example 1: All checks pass → returns True
  • Example 2: Duplicate ‘8’ in top-left box triggers boxes[0] & bit check at (2,2)
  • All Empty: Loop skips all cells, returns True
  • Single Digit: All bitmask operations succeed, returns True

5. Complexity War Room

Hardware-Aware Analysis

  • 27 integers × 4 bytes = 108 bytes total memory
  • Fits entirely in L1 cache (typically 32-64KB)
  • 81 iterations negligible even on embedded systems

Industry Comparison Table

Approach Time Space Readability Interview Viability
Triple Pass O(1) O(1) 10/10 ✅ Good baseline
Bitmask Single Pass O(1) O(1) 7/10 ✅ Optimal choice
Hash Set Single Pass O(1) O(1) 9/10 ✅ Most readable
Array Counting O(1) O(1) 6/10 ❌ Overkill

6. Pro Mode Extras

Variants Section

  • Sudoku Solver (LC 37): Backtracking with same validation
  • N×N Sudoku: Generalize indexing formulas
  • Multiple Solutions Check: Count valid completions
  • Samurai Sudoku: Overlapping board validation

Interview Cheat Sheet

  • First Mention: “This is O(1) time/space due to fixed board size”
  • Key Insight: “Encode seen digits via bitmasking for compact storage”
  • Box Index Formula: 3*(i//3) + j//3 maps (row,col) to box 0-8
  • Testing Strategy: Check duplicates in same row/column/box separately
  • Common Trap: “Remember empty cells don’t count toward duplicates”