-
Notifications
You must be signed in to change notification settings - Fork 0
037 — Valid Sudoku
LeetCode 36 · Medium. Given a 9x9 Sudoku board, partially filled, determine if the filled cells so far satisfy the rules: each digit 1-9 must appear at most once in each row, each column, and each of the nine 3x3 sub-boxes. Empty cells are marked '.' and can be ignored — you're validating the current state, not solving the puzzle.
Picture three referees watching the same Sudoku board at once: one referee tracks each row and blows a whistle the moment a row repeats a digit, a second referee does the same for every column, and a third does the same for every 3x3 box. Each referee only needs a scratch pad per lane they're watching — "which digits have I already seen in this row/column/box?" As soon as any single referee sees a digit they've already noted for their current lane, the board is invalid. No referee ever needs to look back across the whole board — they just keep three running tallies (row, column, box) and check them as they scan through once.
"No duplicates allowed within each row / column / sub-region" — several overlapping "no repeats" constraints checked simultaneously over a grid — is the signal to run one hash set per constraint group (one set per row, one per column, one per box), indexed by a formula that maps a cell's position to which group(s) it belongs to. Whenever a problem says "validate that no group repeats a value" across more than one grouping of the same grid, that's a cue to track membership per group with hash sets rather than re-scanning the grid for every check.
For every filled cell, scan the rest of its row, the rest of its column, and the rest of its 3x3 box, looking for the same digit.
func isValidSudokuBruteForce(_ board: [[Character]]) -> Bool {
let n = 9
for r in 0..<n {
for c in 0..<n {
let value = board[r][c]
if value == "." { continue }
// scan the rest of the row
for cc in 0..<n where cc != c {
if board[r][cc] == value { return false }
}
// scan the rest of the column
for rr in 0..<n where rr != r {
if board[rr][c] == value { return false }
}
// scan the rest of the 3x3 box
let boxRowStart = (r / 3) * 3
let boxColStart = (c / 3) * 3
for rr in boxRowStart..<(boxRowStart + 3) {
for cc in boxColStart..<(boxColStart + 3) {
if (rr != r || cc != c) && board[rr][cc] == value {
return false
}
}
}
}
}
return true
}Big-O: O(n³) time for an n x n board (here n = 9, fixed) — for each of the n² cells, checking its row, column, and box each costs O(n). O(1) extra space.
Make one pass over the board. For each cell, maintain a hash set per row, per column, and per box; before adding a digit to its three sets, check whether it's already in any of them.
func isValidSudoku(_ board: [[Character]]) -> Bool {
var rows = [Set<Character>](repeating: [], count: 9)
var cols = [Set<Character>](repeating: [], count: 9)
var boxes = [Set<Character>](repeating: [], count: 9)
for r in 0..<9 {
for c in 0..<9 {
let value = board[r][c]
if value == "." { continue }
let boxIndex = (r / 3) * 3 + (c / 3)
if rows[r].contains(value) || cols[c].contains(value) || boxes[boxIndex].contains(value) {
return false
}
rows[r].insert(value)
cols[c].insert(value)
boxes[boxIndex].insert(value)
}
}
return true
}Big-O: O(n²) time for an n x n board — a single pass over every cell, with O(1) average per hash-set membership check/insert. O(n²) space for the row/column/box sets combined (each of the 3n sets can hold up to n elements).
The brute force answers "has this digit already appeared in my row/column/box?" by re-scanning that whole row/column/box from scratch, for every single cell — the same cells get re-examined over and over. The optimal solution instead recognizes that "have I seen this digit in this group before?" is a running membership question, which a hash set answers in O(1) if you maintain it incrementally as you sweep the board once. The boxIndex = (r / 3) * 3 + (c / 3) formula is the one extra trick: it maps any (row, col) to one of nine box IDs, letting a flat array of sets stand in for the 2D grid-of-3x3-regions without ever needing nested box coordinates.
- Hash Maps & Hash Sets — the per-row/column/box membership sets this solution is built on.
- Matrix Traversal — the single-pass grid-sweeping shape this solution follows.
- Arrays & Strings — the 2D board representation being traversed.
Valid Sudoku is three referees watching one board — each keeping a running scratch pad per row, column, or box, blowing the whistle the instant a lane repeats.
The boxIndex formula is (r / 3) * 3 + (c / 3). Compute boxIndex by hand for cells (0, 0), (2, 5), and (8, 8), and explain in words what range of rows and columns each resulting box index corresponds to.
⬅️ Previous: Product of Array Except Self · Next: Encode and Decode Strings ➡️