Problem
Given a 9 x 9 Sudoku board, determine whether the board is valid. Only the filled cells need to be validated.A valid Sudoku board must have no repeated digits from
1 to 9 in the same row, column, or 3 x 3 sub-box.
Example(s)
Consider the following examples to understand the expected input and output.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
trueExample 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
falseSolution
This solution uses the HashSet pattern. We maintain three sets for each row, column, and 3 x 3 box.For every filled cell, we check whether the digit already exists in its row, column, or corresponding box. If it exists in any of them, the board is invalid.
The 3 x 3 box containing a cell at position
(i, j) can be identified using (i / 3) * 3 + j / 3. Here, (i / 3) * 3 identifies the starting row of the box, while j / 3 identifies the box within that row. This gives each box a unique index from 0 to 8.
class Solution {
public boolean isValidSudoku(char[][] board) {
Set<Character>[] rows = new HashSet[9];
Set<Character>[] columns = new HashSet[9];
Set<Character>[] boxes = new HashSet[9];
for (int i = 0; i < 9; i++) {
rows[i] = new HashSet<>();
columns[i] = new HashSet<>();
boxes[i] = new HashSet<>();
}
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char value = board[i][j];
if (value == '.') {
continue;
}
int box = (i / 3) * 3 + j / 3;
if (!rows[i].add(value) ||
!columns[j].add(value) ||
!boxes[box].add(value)) {
return false;
}
}
}
return true;
}
}Complexity
The board has a fixed size of 9 x 9, so we inspect every cell once. The time complexity isO(1) for a standard Sudoku board, or O(n2) for a generalized n x n board.
The three sets store the digits for rows, columns, and boxes, giving
O(1) space for the standard board.