Valid Sudoku
You're given a 9 x 9 Sudoku board, partly filled. Each cell holds a digit from 1 to 9 or a dot for an empty cell. Return true if the filled cells break none of the rules: no digit repeats within a row, within a column, or within any of the nine 3 x 3 boxes. Only the filled cells are checked; the board does not have to be solvable.
Examples
board = ["5.......3", ".2...7...", "..9..1...", "...3.....", "7...6...2", ".....8...", "...2..8..", "...4...1.", "6.......4"] returns true
Each string is one row. No row, column, or box holds the same digit twice.
board = ["5.......3", ".2...7...", "2.9..1...", "...3.....", "7...6...2", ".....8...", "...2..8..", "...4...1.", "6.......4"] returns false
The 2 added at row 2, column 0 is fine for its row and its column, but the top-left box already has a 2 at row 1, column 1.
board = ["5.......3", ".2...7...", "..9..1...", "...3.....", "7...6...2", ".....8...", "...2..8..", "...4...1.", "5.......4"] returns false
Column 0 now holds a 5 in both the first and the last row.
Constraints
- board.length == 9 and board[i].length == 9
- board[i][j] is a digit from 1 to 9 or '.'.
Hints
Every filled cell belongs to exactly one row, one column, and one box. What do you need to remember about each of those groups as you scan?
Keep a hash set per row, per column, and per 3 x 3 box, and check membership before you insert.
For each filled cell (r, c), compute b = (r / 3) * 3 + c / 3. If the digit is in rows[r], cols[c], or boxes[b], return false; otherwise add it to all three.
Drill This: Your Approach First
Approach
Make one pass over the 81 cells and keep a set of seen digits for every row, every column, and every box. Box index is (r / 3) * 3 + c / 3 with integer division, which numbers the nine boxes 0 to 8 in reading order. For each filled cell, if its digit is already in the cell's row set, column set, or box set, return false; otherwise add it to all three. The board is a fixed 9 x 9, so this is O(1) time and space, or O(n^2) for an n x n generalization.
Time
O(81)
Space
O(81)
Pitfall
Solutions
class Solution {
public boolean isValidSudoku(char[][] board) {
boolean[][] rows = new boolean[9][9];
boolean[][] cols = new boolean[9][9];
boolean[][] boxes = new boolean[9][9];
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
char ch = board[r][c];
if (ch == '.') continue;
int d = ch - '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;
}
}class Solution:
def isValidSudoku(self, board) -> 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):
d = board[r][c]
if d == ".":
continue
b = (r // 3) * 3 + c // 3
if d in rows[r] or d in cols[c] or d in boxes[b]:
return False
rows[r].add(d)
cols[c].add(d)
boxes[b].add(d)
return True