LeetCode · #36

Valid Sudoku Solution

Determine if a 9×9 Sudoku board is valid. Only the filled cells need to be validated — each row, column, and 3×3 sub-box must contain the digits 1–9 without repetition.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #36

🏗️

Pattern

Hash Set — duplicate detection

Determine if a 9 × 9 Sudoku board is valid. Only the filled cells need to be validated according to three rules: each row, each column, and each of the nine 3×3 sub-boxes must contain the digits 1–9 without repetition.

Key Rules

 • Each row must contain 1–9 with no duplicates • Each column must contain 1–9 with no duplicates • Each of the nine 3×3 sub-boxes must contain 1–9 with no duplicates • Empty cells are represented as '.' • Board is always 9×9 

Constraints

 • board.length == 9 • board[i].length == 9 • board[i][j] is a digit '1'-'9' or '.'  ↑ Fixed 9×9 grid — all operations are O(81) = O(1) 

Section Two · Approach 1

Brute Force — Three Separate Scans

Validate rows with one pass, columns with another, and 3×3 boxes with a third. Each scan uses a fresh HashSet to check for duplicates. Three loops over 81 cells = 243 cell visits.

Why it works

Checking each constraint independently guarantees correctness. If any row, column, or box has a duplicate digit, return false.

Why we can do better

Problem: We scan the board three times. Since the board is fixed at 9×9, the constant factor doesn't matter asymptotically — but a single-pass solution is cleaner and more elegant. We can track all three constraints simultaneously with 27 HashSets (9 rows + 9 columns + 9 boxes).

Java — Three Scans

 import java.util.HashSet;
class Solution {
public boolean isValidSudoku(char[][] board) {
// Check rows for (int r = 0; r < 9; r++) {
HashSet<Character> seen = new HashSet<>();
for (int c = 0; c < 9; c++)
if (board[r][c] != '.' && !seen.add(board[r][c])) return false;
        }
// Check columns for (int c = 0; c < 9; c++) {
HashSet<Character> seen = new HashSet<>();
for (int r = 0; r < 9; r++)
if (board[r][c] != '.' && !seen.add(board[r][c])) return false;
        }
// Check 3×3 boxes for (int br = 0; br < 3; br++)
for (int bc = 0; bc < 3; bc++) {
HashSet<Character> seen = new HashSet<>();
for (int r = br*3; r < br*3+3; r++)
for (int c = bc*3; c < bc*3+3; c++)
if (board[r][c] != '.' && !seen.add(board[r][c])) return false;
            }
return true;
    }
}

Python — Three Scans

 class Solution:
def isValidSudoku(self, board: list[list[str]]) -> bool:
for r in range(9):
            seen = set()
for c in range(9):
if board[r][c] != '.':
if board[r][c] in seen: return False
seen.add(board[r][c])
# similar for columns and boxes... return True 

Metric	Value
Time	O(81) = O(1) — fixed board size, three passes
Space	O(27) = O(1) — 27 sets of max 9 elements each

Section Three · Approach 2

Single-Pass HashSet — O(1)

Scan the board once. For each cell, check three constraints simultaneously using prebuilt HashSets for each row, column, and box. The box index for cell (r,c) is (r/3) * 3 + (c/3).

💡 Mental model: Imagine three librarians at a desk, each maintaining a different catalog: one tracks digits per shelf-row, one per column, one per section. As each book (digit) arrives, all three librarians check their catalogs simultaneously. If any catalog says "already recorded," it's a duplicate — invalid. One pass through the incoming books, three parallel checks.

Algorithm — Parallel constraint tracking

Step 1: Create 9 HashSets for rows, 9 for columns, 9 for boxes.
Step 2: For each cell (r, c), skip if '.'.
Step 3: Compute box index: boxIdx = (r/3) * 3 + (c/3).
Step 4: If the digit exists in rows[r], cols[c], or boxes[boxIdx] → return false.
Step 5: Add the digit to all three sets. Continue.
Step 6: If we complete the loop → return true.

🎯 When to recognize this pattern:

Any problem that requires checking multiple overlapping constraints over a grid — think parallel set tracking.
The signal is "validate rows AND columns AND sub-regions." This same approach works for N-Queens validation, crossword constraint checking, and any grid-based uniqueness problem.

The box index formula:

(r/3) * 3 + (c/3) maps each cell to a box 0–8.
Integer division r/3 gives the box-row (0, 1, or 2), and c/3 gives the box-column.
Multiplying the box-row by 3 and adding the box-column gives a unique index for all 9 boxes.

Section Four · Trace

Visual Walkthrough

How the box index maps cells to 3×3 boxes:

Box Index Formula — (r/3)*3 + (c/3)

Notice:

One loop over 81 cells, three set lookups per cell. Every constraint is checked in parallel — no separate passes needed.
The box index formula is the key insight that makes single-pass validation possible.

Section Five · Implementation

Code — Java & Python

Java — Single-Pass HashSet

 import java.util.HashSet;
class Solution {
public boolean isValidSudoku(char[][] board) {
HashSet<Character>[] rows = new HashSet[9];
HashSet<Character>[] cols = new HashSet[9];
HashSet<Character>[] boxes = new HashSet[9];
for (int i = 0; i < 9; i++) {
            rows[i] = new HashSet<>();
            cols[i] = new HashSet<>();
            boxes[i] = new HashSet<>();
        }
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
char val = board[r][c];
if (val == '.') continue;
int boxIdx = (r / 3) * 3 + (c / 3); // maps to box 0–8 if (!rows[r].add(val) ||
                    !cols[c].add(val) ||
                    !boxes[boxIdx].add(val))
return false; // duplicate in row, col, or box
}
        }
return true;
    }
}

Python — Single-Pass set

 class Solution:
def isValidSudoku(self, board: list[list[str]]) -> bool:
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]
for r in range(9):
for c in range(9):
                val = board[r][c]
if val == '.':
continue
box_idx = (r // 3) * 3 + (c // 3)
if (val in rows[r] or
val in cols[c] or
val in boxes[box_idx]):
return False
rows[r].add(val)
                cols[c].add(val)
                boxes[box_idx].add(val)
return True 

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Three Separate Scans	O(81) = O(1)	O(27)	Three passes; conceptually clear but redundant
Encoding into single set	O(81) = O(1)	O(81)	Uses encoded strings like "r0-5" — clever but harder to read
Single-Pass 27 Sets ← optimal	O(81) = O(1)	O(27) = O(1)	One pass, three parallel checks. Clean and efficient.

Is it really O(1)?:

Yes — the board is always 9×9 = 81 cells. Time and space are bounded by constants regardless of input.
In Big-O terms, this is O(1).
Some interviewers prefer to see O(n²) where n=9, to show you understand the generalization to n×n Sudoku.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Mostly empty	Board with 1–2 filled cells	Valid — no duplicates possible with so few cells.
Row duplicate	Same digit twice in one row	Caught by rows[r] set on second occurrence.
Column duplicate	Same digit twice in one column	Caught by cols[c] set.
Box duplicate	Same digit in same 3×3 box	Caught by boxes[boxIdx]. The tricky constraint to catch.
Cross-box same digit	Same digit in different boxes	Valid — digits can repeat across different rows/cols/boxes.
Fully filled valid board	Complete valid Sudoku	All 81 cells checked, all pass → true.

⚠ Common Mistake: Using r / 3 + c / 3 instead of (r / 3) * 3 + (c / 3) for the box index. The wrong formula maps cells (0,3) and (3,0) to the same box — but they belong to boxes 1 and 3 respectively. The multiplication by 3 ensures each box-row gets its own range of indices.

← Back to Arrays & Hashing problems

LearningTree

LC 36 · Valid Sudoku — Solution & Explanation | DSA Guide