#36
Valid Sudoku
Medium Row/column/box sets
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Check whether a partially filled 9×9 Sudoku board breaks any rule: no digit repeats in a row, a column or a 3×3 box. The puzzle doesn't need to be solvable.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: does any row, column or 3×3 box repeat a digit?
Why this works: remember which digits each row, column and box has seen. Box number = (r/3)·3 + c/3.
Example: a '5' at (0,0) and another '5' at (1,1)
both in box 0 → repeat → false✦Hints open one at a time
Keep a "seen" record for each row, column and box.
The box index of cell (r, c) is (r / 3) * 3 + c / 3.
↗Approach
Use three 9×9 boolean arrays. For each filled cell, if the digit was already seen in its row, column or box, return false; otherwise mark it.
</>Solution (Java)
class Solution {
public boolean isValidSudoku(char[][] board) {
boolean[][] rows = new boolean[9][9], cols = new boolean[9][9], boxes = new boolean[9][9];
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
if (board[r][c] == '.') continue;
int d = board[r][c] - '1';
int b = (r / 3) * 3 + c / 3;
if (rows[r][d] || cols[c][d] || boxes[b][d]) return false;
rows[r][d] = cols[c][d] = boxes[b][d] = true;
}
}
return true;
}
}!Common mistake
Computing the box index as r / 3 + c / 3, which maps different boxes to the same index.
Complexity
- Time: O(81) = O(1).
- Space: O(1).
Topic: 2D Arrays & Matrix
🎬 Episode 14: video coming soon