🎨Now live: Try our Free AI Image Generation Feature

Intuition
The problem requires us to check if a given partially filled 9x9 Sudoku board is valid. The key point is that we only need to validate the filled cells according to the Sudoku rules:
- Each row must contain the digits 1-9 without repetition.
- Each column must contain the digits 1-9 without repetition.
- Each of the nine 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.
By keeping track of the numbers seen so far in each row, column, and 3x3 sub-box, we can efficiently validate the board as we iterate through each cell.
Approach
- Initialization: - Use three lists of dictionaries to track the numbers seen in each row, column, and 3x3 sub-box. Each list has 9 dictionaries, one for each row, column, and sub-box.
- Iterate through the board:
- Loop through each cell in the 9x9 grid using nested loops for rows and columns.
- For each cell that contains a number (not '.'), do the following:
- Calculate the index of the corresponding 3x3 sub-box.
- Check if the number already exists in the current row, column, or sub-box using the respective dictionaries.
- If the number is already present in any of the dictionaries, the board is not valid, so return
false
. - If the number is not present, mark it as seen in the respective dictionaries for the current row, column, and sub-box. - Return the result:
- If the entire board is processed without finding any conflicts, return
true
, indicating the Sudoku board is valid.
Complexity
Time Complexity:
O(1)
- The board size is fixed at 9x9, so the operations are bounded and do not scale with input size.
Space Complexity:
O(1)
- We use a fixed amount of extra space for the dictionaries, which do not grow with input size. Each dictionary can contain at most 9 entries, corresponding to the digits 1-9.
Code
C++
class Solution {
public:
bool isValidSudoku(vector>& board) {
vector> rows(9);
vector> cols(9);
vector> boxes(9);
for (int r = 0; r < 9; ++r) {
for (int c = 0; c < 9; ++c) {
if (board[r][c] != '.') {
char num = board[r][c];
int boxIndex = (r / 3) * 3 + (c / 3);
if (rows[r][num] || cols[c][num] || boxes[boxIndex][num]) {
return false;}
rows[r][num] = true;
cols[c][num] = true;
boxes[boxIndex][num] = true;
}
}
}
return true;
}
};
Python
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
rows = [{} for _ in range(9)]
cols = [{} for _ in range(9)]
boxes = [{} for _ in range(9)]
for r in range(9):
for c in range(9):
if board[r][c] != '.':
num = board[r][c]
box_index = (r // 3) * 3 + (c // 3)
if num in rows[r] or num in cols[c] or num in boxes[box_index]:
return False
rows[r][num] = True
cols[c][num] = True
boxes[box_index][num] = True
return True
Java
class Solution {
public boolean isValidSudoku(char[][] board) {
HashMap[] rows = new HashMap[9];
HashMap[] cols = new HashMap[9];
HashMap[] boxes = new HashMap[9];
for (int i = 0; i < 9; i++) {
rows[i] = new HashMap<>();
cols[i] = new HashMap<>();
boxes[i] = new HashMap<>();}
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
if (board[r][c] != '.') {
char num = board[r][c];
int boxIndex = (r / 3) * 3 + (c / 3);
if (rows[r].getOrDefault(num, false) || cols[c].getOrDefault(num, false) || boxes[boxIndex].getOrDefault(num, false)) {
return false;}
rows[r].put(num, true);
cols[c].put(num, true);
boxes[boxIndex].put(num, true);
}
}
}
return true;
}}
JavaScript
var isValidSudoku = function(board) {
let rows = new Array(9).fill(0).map(() => ({}))
let cols = new Array(9).fill(0).map(() => ({}))
let box = new Array(9).fill(0).map(() => ({}))
for(let r = 0; r < 9; r++){
for(let c = 0; c < 9; c++){
if(board[r][c] !== "."){
let num = board[r][c]
let boxIndex = Math.floor(r / 3) * 3 + Math.floor(c / 3)
if(rows[r][num] || cols[c][num] || box[boxIndex][num]){
return false}
rows[r][num] = true
cols[c][num] = true
box[boxIndex][num] = true
}
}}
return true
};