Skip to content

9. Valid Sudoku

🔗 LeetCode Problem: 36. Valid Sudoku
📊 Difficulty: Medium
🏷️ Topics: Array, Hash Table, Matrix

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 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 '.'

🎨 Visual Understanding

The Three Rules Visualized

Rule 1: Each ROW must have unique digits (no duplicates)

Row 0: [5, 3, ., ., 7, ., ., ., .]
       All filled cells different ✓

Row 1: [6, ., ., 1, 9, 5, ., ., .]
       6, 1, 9, 5 all different ✓


Rule 2: Each COLUMN must have unique digits

Column 0: [5, 6, ., 8, 4, 7, ., ., .]
          5, 6, 8, 4, 7 all different ✓


Rule 3: Each 3x3 BOX must have unique digits

Box 0 (top-left):
┌─────┬─────┬─────┐
│  5  │  3  │  .  │
├─────┼─────┼─────┤
│  6  │  .  │  .  │
├─────┼─────┼─────┤
│  .  │  9  │  8  │
└─────┴─────┴─────┘
5, 3, 6, 9, 8 all different ✓

Board Layout with Box Indices

The 9x9 board is divided into 9 boxes (numbered 0-8):

┌─────────┬─────────┬─────────┐
│         │         │         │
│  Box 0  │  Box 1  │  Box 2  │
│         │         │         │
├─────────┼─────────┼─────────┤
│         │         │         │
│  Box 3  │  Box 4  │  Box 5  │
│         │         │         │
├─────────┼─────────┼─────────┤
│         │         │         │
│  Box 6  │  Box 7  │  Box 8  │
│         │         │         │
└─────────┴─────────┴─────────┘

Box calculation for cell (row, col):
  boxIndex = (row / 3) * 3 + (col / 3)

Examples:
  (0, 0) → box 0
  (0, 5) → box 1
  (4, 4) → box 4
  (8, 8) → box 8

Invalid Example Visualization

Invalid case: Two 8's in same row

Row 0: [8, 3, ., ., 7, ., ., ., .]
        ↑
Row 3: [8, ., ., ., 6, ., ., ., 3]
        ↑
        Both in Column 0 → INVALID ✗

Also invalid in Box 0:
┌─────┬─────┬─────┐
│  8  │  3  │  .  │  ← 8 here
├─────┼─────┼─────┤
│  6  │  .  │  .  │
├─────┼─────┼─────┤
│  8  │  .  │  .  │  ← 8 here (duplicate!)
└─────┴─────┴─────┘

🎯 Approach 1: Brute Force (Check Each Rule Separately)

The Most Natural Thinking 💭

Core Logic: 

Check all three rules independently:

1. Check all rows: For each row, verify no duplicate digits
2. Check all columns: For each column, verify no duplicate digits  
3. Check all boxes: For each 3x3 box, verify no duplicate digits

Use HashSet to detect duplicates in each check

Why This Works: - Directly implements the three rules - Easy to understand and debug - Clear separation of concerns

Why This is Suboptimal: - Scans the board 3 times (once per rule) - Creates many temporary HashSets - More code to write and maintain

Implementation

public boolean isValidSudoku(char[][] board) {
    // Check all rows
    for (int row = 0; row < 9; row++) {
        if (!isValidUnit(board, row, 0, 0, 1)) {
            return false;
        }
    }

    // Check all columns
    for (int col = 0; col < 9; col++) {
        if (!isValidUnit(board, 0, col, 1, 0)) {
            return false;
        }
    }

    // Check all 3x3 boxes
    for (int box = 0; box < 9; box++) {
        int startRow = (box / 3) * 3;
        int startCol = (box % 3) * 3;
        if (!isValidBox(board, startRow, startCol)) {
            return false;
        }
    }

    return true;
}

// Check a row or column for duplicates
private boolean isValidUnit(char[][] board, int startRow, int startCol, 
                            int rowDelta, int colDelta) {
    HashSet<Character> seen = new HashSet<>();
    int row = startRow, col = startCol;

    for (int i = 0; i < 9; i++) {
        char c = board[row][col];
        if (c != '.') {
            if (seen.contains(c)) return false;
            seen.add(c);
        }
        row += rowDelta;
        col += colDelta;
    }
    return true;
}

// Check a 3x3 box for duplicates
private boolean isValidBox(char[][] board, int startRow, int startCol) {
    HashSet<Character> seen = new HashSet<>();

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            char c = board[startRow + i][startCol + j];
            if (c != '.') {
                if (seen.contains(c)) return false;
                seen.add(c);
            }
        }
    }
    return true;
}

⏰ Time: O(81) = O(1) - board size fixed, but 3 passes
💾 Space: O(9) = O(1) - HashSets of max size 9

✅ Approach 2: Single Pass with Three HashSets (Optimal)

The Breakthrough Insight 💡

Core Logic: 

Key Observation:
We can check all three rules in a SINGLE pass!

Strategy:
Maintain three arrays of HashSets:
- rows[9]: HashSet for each row
- cols[9]: HashSet for each column  
- boxes[9]: HashSet for each 3x3 box

For each cell (i, j):
1. If cell is '.', skip it
2. Check if digit already in rows[i] → duplicate!
3. Check if digit already in cols[j] → duplicate!
4. Check if digit already in boxes[boxIndex] → duplicate!
5. If no duplicates, add to all three sets

Box Index Formula: 

For cell at (row, col):
  boxIndex = (row / 3) * 3 + (col / 3)

Why this works:
- row / 3 gives which row of boxes (0, 1, or 2)
- col / 3 gives which column of boxes (0, 1, or 2)
- Formula maps to 0-8

Examples:
  (0,0) → (0/3)*3 + (0/3) = 0*3 + 0 = 0
  (0,5) → (0/3)*3 + (5/3) = 0*3 + 1 = 1
  (4,4) → (4/3)*3 + (4/3) = 1*3 + 1 = 4
  (8,8) → (8/3)*3 + (8/3) = 2*3 + 2 = 8

Why This is Better: - Single pass through board - All checks done simultaneously - Less code, easier to maintain - Early termination on first duplicate

Implementation

public boolean isValidSudoku(char[][] board) {
    // Create HashSets for rows, columns, and boxes
    HashSet<Character>[] rows = new HashSet[9];
    HashSet<Character>[] cols = new HashSet[9];
    HashSet<Character>[] boxes = new HashSet[9];

    // Initialize all HashSets
    for (int i = 0; i < 9; i++) {
        rows[i] = new HashSet<>();
        cols[i] = new HashSet<>();
        boxes[i] = new HashSet<>();
    }

    // Single pass through the board
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            char c = board[i][j];

            // Skip empty cells
            if (c == '.') continue;

            // Calculate which box this cell belongs to
            int boxIndex = (i / 3) * 3 + (j / 3);

            // Check for duplicates
            if (rows[i].contains(c) || 
                cols[j].contains(c) || 
                boxes[boxIndex].contains(c)) {
                return false;  // Duplicate found!
            }

            // Add to all three sets
            rows[i].add(c);
            cols[j].add(c);
            boxes[boxIndex].add(c);
        }
    }

    return true;  // No duplicates found
}

Step-by-Step Execution: board with duplicate 8's

Board (simplified view, focusing on key cells):
Row 0: [8, 3, ., ., ., ., ., ., .]
Row 3: [8, ., ., ., ., ., ., ., .]

Initial Setup:
═══════════════════════════════════════════════════════════════════
rows[0..8] = empty HashSets
cols[0..8] = empty HashSets
boxes[0..8] = empty HashSets
═══════════════════════════════════════════════════════════════════

Processing:

Cell (0,0) = '8':
├─ boxIndex = (0/3)*3 + (0/3) = 0
├─ Check rows[0]: empty → no duplicate ✓
├─ Check cols[0]: empty → no duplicate ✓
├─ Check boxes[0]: empty → no duplicate ✓
├─ Add '8' to rows[0]: {8}
├─ Add '8' to cols[0]: {8}
└─ Add '8' to boxes[0]: {8}

Cell (0,1) = '3':
├─ boxIndex = (0/3)*3 + (1/3) = 0
├─ Check rows[0]: {8} → '3' not found ✓
├─ Check cols[1]: empty → no duplicate ✓
├─ Check boxes[0]: {8} → '3' not found ✓
├─ Add '3' to rows[0]: {8, 3}
├─ Add '3' to cols[1]: {3}
└─ Add '3' to boxes[0]: {8, 3}

... (skip empty cells and other cells)

Cell (3,0) = '8':
├─ boxIndex = (3/3)*3 + (0/3) = 1*3 + 0 = 3
├─ Check rows[3]: empty → no duplicate ✓
├─ Check cols[0]: {8, 6, ...} → '8' FOUND! ✗
└─ DUPLICATE IN COLUMN 0!
   Return false immediately

═══════════════════════════════════════════════════════════════════
🎯 RESULT: false (found duplicate '8' in column 0)
═══════════════════════════════════════════════════════════════════

Valid Board Example: All checks pass

Board (simplified):
[["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"]]

Cell (0,0) = '5':
  rows[0].add('5'), cols[0].add('5'), boxes[0].add('5')

Cell (0,1) = '3':
  rows[0].add('3'), cols[1].add('3'), boxes[0].add('3')

... continue for all cells

After scanning entire board:
- No duplicates found in any row
- No duplicates found in any column
- No duplicates found in any box

Result: true ✓

⏰ Time: O(81) = O(1) - single pass, fixed board size
💾 Space: O(81) = O(1) - max 27 HashSets with 9 elements each

🎯 Approach 3: String Encoding (Most Elegant)

Thought Process 💭

Core Logic: 

Instead of maintaining separate HashSet arrays,
use a SINGLE HashSet with encoded strings!

Encoding scheme:
- Row check: "5 in row 0"
- Column check: "5 in col 2"
- Box check: "5 in box 4"

All strings go into one HashSet
If string already exists → duplicate!

Why This is Elegant: - Single HashSet instead of 27 - More concise code - Same efficiency - Easy to read and understand

Implementation

public boolean isValidSudoku(char[][] board) {
    HashSet<String> seen = new HashSet<>();

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            char c = board[i][j];

            if (c != '.') {
                // Create three encoded strings
                String row = c + " in row " + i;
                String col = c + " in col " + j;
                String box = c + " in box " + (i/3)*3 + (j/3);

                // Check if any already exist
                if (!seen.add(row) || !seen.add(col) || !seen.add(box)) {
                    return false;
                }
            }
        }
    }

    return true;
}

Step-by-Step Execution

Cell (0,0) = '5':
├─ Create: "5 in row 0"
├─ Create: "5 in col 0"
├─ Create: "5 in box 0"
├─ Add all three to seen
└─ seen = {"5 in row 0", "5 in col 0", "5 in box 0"}

Cell (0,1) = '3':
├─ Create: "3 in row 0"
├─ Create: "3 in col 1"
├─ Create: "3 in box 0"
├─ Add all three to seen
└─ seen = {..., "3 in row 0", "3 in col 1", "3 in box 0"}

Cell (1,0) = '6':
├─ Create: "6 in row 1"
├─ Create: "6 in col 0"
├─ Create: "6 in box 0"
├─ Try to add to seen
└─ All added successfully (no duplicates)

If we encounter duplicate:
Cell (3,0) = '8' (but '8' already in col 0):
├─ Create: "8 in row 3"
├─ Create: "8 in col 0"
├─ Try to add "8 in col 0" → ALREADY EXISTS!
└─ Return false

⏰ Time: O(1) - fixed 81 cells
💾 Space: O(1) - max 81*3 = 243 strings

🔍 Edge Cases

Case 1: Empty board (all '.')
Input: All cells are '.'
Output: true
Reason: No filled cells to violate rules

Case 2: Single filled cell
Input: One '5', rest are '.'
Output: true

Case 3: Duplicate in same row
Input: ['5', '3', '5', ., ., ., ., ., .]
Output: false
Reason: Two 5's in row 0

Case 4: Duplicate in same column
Input: 
  Row 0: ['5', ., ., ...]
  Row 1: ['5', ., ., ...]
Output: false

Case 5: Duplicate in same box
Input:
  ┌───┬───┬───┐
  │ 5 │ . │ . │
  │ . │ 5 │ . │
  │ . │ . │ . │
  └───┴───┴───┘
Output: false

Case 6: Valid but unsolvable
Input: Valid board that cannot be solved
Output: true
Reason: We only check validity, not solvability

Case 7: All same digit in different regions
Input: '1' in all 9 boxes but different rows/cols
Output: Could be valid if placed correctly

Case 8: Maximum filled (no empty cells)
Input: Complete valid sudoku solution
Output: true

Common Mistakes

Mistake 1: Wrong box index calculation
❌ Wrong: boxIndex = i/3 + j/3
✓ Right: boxIndex = (i/3)*3 + (j/3)

Mistake 2: Not skipping empty cells
❌ Wrong: Check '.' as if it's a digit
✓ Right: if (c == '.') continue;

Mistake 3: Creating new HashSet each time
❌ Wrong: HashSet<Character> set = new HashSet<>(); inside loop
✓ Right: Create once, reuse or use array of sets

Mistake 4: Not checking all three conditions
❌ Wrong: Only check rows and columns
✓ Right: Must check rows, columns, AND boxes

Mistake 5: Off-by-one in box calculation
❌ Wrong: Confusion between 0-indexed and 1-indexed
✓ Right: Use integer division (i/3, j/3)

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Three Separate Passes
  Time: O(1) but 3 passes
  Space: O(1)
  Use: When code clarity most important

Approach 2: Single Pass with Arrays (RECOMMENDED)
  Time: O(1) single pass
  Space: O(1)
  Use: Best balance of clarity and efficiency

Approach 3: String Encoding (MOST ELEGANT)
  Time: O(1)
  Space: O(1)
  Use: Most concise code

🔑 The Core Insight

Sudoku validation = Three independent checks:
1. Row uniqueness
2. Column uniqueness
3. Box uniqueness

Optimization: Do all checks in ONE pass
→ Use HashSets to detect duplicates
→ Box index formula: (row/3)*3 + (col/3)

Single pass beats three passes
→ Same complexity but faster in practice

🎯 Pattern Recognition

Problem Type: Matrix Validation with Multiple Constraints
Core Pattern: HashSet for duplicate detection

When to Apply:
✓ Need to validate uniqueness in multiple dimensions
✓ Matrix has regions with constraints
✓ Can process in single pass
✓ Fixed size constraints

Key Techniques:
→ HashSet array for tracking seen elements
→ Index formula for mapping cells to regions
→ Early termination on first violation

Related Problems:
- Sudoku Solver (LC 37)
- N-Queens (LC 51)
- Valid Tic-Tac-Toe State (LC 794)

🧠 Interview Strategy

Step 1: "Need to check three rules: rows, columns, boxes"
Step 2: "Can check each rule separately - 3 passes"
Step 3: "Better: check all rules in single pass"
Step 4: "Use HashSets to detect duplicates"
Step 5: "Box index formula: (row/3)*3 + (col/3)"

📝 Quick Revision Notes

🎯 Core Concept:

Validate sudoku by checking no duplicates in any row, column, or 3x3 box. Use HashSets to track seen digits in single pass.

⚡ Quick Implementation:

public boolean isValidSudoku(char[][] board) {
    // // Approach 1 - using 27 hashset
    // Set<Character>[] rows = new HashSet[9];
    // Set<Character>[] cols = new HashSet[9];
    // Set<Character>[] box = new HashSet[9];

    // // Initialize all 27 hashset
    // for(int i = 0; i < 9; i++) {
    //     rows[i] = new HashSet<>();
    //     cols[i] = new HashSet<>();
    //     box[i] = new HashSet<>();
    // }

    // // Iterate through every cell and fill the above sets and decide.
    // for(int i = 0; i < board.length; i++) {
    //     for(int j = 0; j < board[0].length; j++) {
    //         char ch = board[i][j];                
    //         if(ch == '.') {
    //             continue;
    //         }

    //         int boxIndex = (i / 3) * 3 + (j / 3);

    //         if(rows[i].contains(ch) || cols[j].contains(ch) || box[boxIndex].contains(ch)) {
    //             return false;
    //         }

    //         rows[i].add(ch);
    //         cols[j].add(ch);
    //         box[boxIndex].add(ch);
    //     }
    // }

    // return true;

    // Approach 2 - using a single string hashset
    HashSet<String> set = new HashSet<>();
    for(int i = 0; i < board.length; i++) {
        for(int j = 0; j < board[0].length; j++) {
            if(board[i][j] == '.') {
                continue;
            }

            char ch = board[i][j];
            int boxIndex = (i / 3) * 3 + (j / 3);

            String rowText = ch + " found in row " + i;
            String colText = ch + " found in col " + j;
            String boxText = ch + " found in box " + boxIndex;

            if(set.contains(rowText) || set.contains(colText) || set.contains(boxText)) {
                return false;
            }

            set.add(rowText);
            set.add(colText);
            set.add(boxText);
        }
    }

    return true;
}

🔑 Key Insights:

  • Three rules to check: rows, columns, 3x3 boxes
  • Single pass through board checks all rules
  • HashSet detects duplicates efficiently
  • Box index formula: (row/3)*3 + (col/3)
  • String encoding elegant alternative to array of sets
  • Skip empty cells (marked with '.')

🎪 Memory Aid:

"One pass, three checks, box formula (row/3)3 + (col/3)!"
Think: "Row check, col check, box check - all in one loop"*

  • Sudoku Solver (LC 37)
  • N-Queens (LC 51)
  • Valid Tic-Tac-Toe State (LC 794)

Happy practicing! 🎯