Problem Statement
Determine if a 9 x 9 Sudoku board is valid. A valid Sudoku board (partially filled) is not necessarily solvable. It must satisfy the following conditions:
- Each row must contain the digits
1-9without repetition. - Each column must contain the digits
1-9without repetition. - Each of the nine
3 x 3sub-boxes of the grid must contain the digits1-9without repetition.
The Sudoku board can be partially filled, where empty cells are filled with the character '.'.
Constraints:
- The board is a
9 x 9matrix. - Each cell contains either a digit
1-9or the character'.'.
Examples
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: true
Explanation:
Every row contains number from 1 to 9 (ignoring .) without repetition.
Every column contains number from 1 to 9 (ignoring .) without repetition.
There are total 9 sub-boxes. Each contains number from
1-9 without repetition.Example 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: false
Explanation:
The top-left corner has two '8's in the same row, violating the Sudoku rule.Different Approaches
1️⃣ Brute Force Approach (Using Hash sets)
Code:
class Solution {
public:
// Helper function to validate a subgrid (3x3 section) of the Sudoku board.
// Parameters:
// - board: the entire 9x9 board.
// - sr: starting row of the subgrid.
// - er: ending row of the subgrid.
// - sc: starting column of the subgrid.
// - ec: ending column of the subgrid.
// Returns:
// - true if the subgrid is valid (no duplicate numbers), otherwise false.
bool validSub(vector<vector<char>>& board, int sr, int er, int sc, int ec) {
unordered_set<char> st; // A set to track characters in the subgrid.
// Iterate through each cell in the subgrid.
for(int row = sr; row <= er; row++) {
for(int col = sc; col <= ec; col++) {
char ch = board[row][col]; // Get the character at the current cell.
if(ch == '.') continue; // Ignore empty cells.
if(st.count(ch)) return false; // If the character is already in the set, it's a duplicate.
st.insert(ch); // Add the character to the set.
}
}
return true; // If no duplicates, the subgrid is valid.
}
// Main function to validate the entire Sudoku board.
bool isValidSudoku(vector<vector<char>>& board) {
// Step 1: Validate each row.
for(int row = 0; row < 9; row++) {
unordered_set<char> st; // A set to track characters in the current row.
// Traverse each column in the current row.
for(int col = 0; col < 9; col++) {
char ch = board[row][col]; // Get the character in the current cell.
if(ch == '.') continue; // Ignore empty cells.
if(st.count(ch)) return false; // If the character is already in the set, it's a duplicate.
st.insert(ch); // Add the character to the set.
}
}
// Step 2: Validate each column.
for(int col = 0; col < 9; col++) {
unordered_set<char> st; // A set to track characters in the current column.
// Traverse each row in the current column.
for(int row = 0; row < 9; row++) {
char ch = board[row][col]; // Get the character in the current cell.
if(ch == '.') continue; // Ignore empty cells.
if(st.count(ch)) return false; // If the character is already in the set, it's a duplicate.
st.insert(ch); // Add the character to the set.
}
}
// Step 3: Validate each 3x3 sub-box.
for(int sr = 0; sr < 9; sr += 3) { // Traverse starting rows of each 3x3 subgrid.
int er = sr + 2; // Calculate the ending row for the current subgrid.
for(int sc = 0; sc < 9; sc += 3) { // Traverse starting columns of each 3x3 subgrid.
int ec = sc + 2; // Calculate the ending column for the current subgrid.
// Validate the current 3x3 subgrid.
if(!validSub(board, sr, er, sc, ec)) {
return false; // If the subgrid is invalid, return false.
}
}
}
return true; // If all checks pass, the Sudoku board is valid.
}
};
Complexity Analysis:
- Time Complexity:
- Row validation: O(9^2) because we traverse 81 cells in total (9 rows, each with 9 columns).
- Column validation: O(9^2) for the same reason as row validation.
- Subgrid validation: O(9^2) because there are 9 subgrids, and each subgrid has 9 cells. Thus, the overall time complexity is O(3 * 9^2) = O(243), which simplifies to O(1) since the board size is fixed.
- Space Complexity:
- O(1) in terms of additional space (ignoring input), as we only use a few sets to track the elements in rows, columns, and subgrids.
OR
Intuition:
To check if a Sudoku board is valid, we need to ensure:
- No duplicate digits appear in any row.
- No duplicate digits appear in any column.
- No duplicate digits appear in any
3 x 3sub-box.
We can use three sets of hash sets:
- Rows: A list of 9 sets to track digits in each row.
- Columns: A list of 9 sets to track digits in each column.
- Boxes: A list of 9 sets to track digits in each sub-box (calculated based on the current row and column).
Steps:
- Traverse each cell of the board.
- For every non-empty cell (i.e., not '.'), check:
- If the number already exists in the current row, column, or box.
- If so, return
false(invalid board).
- If all checks pass, return
true(valid board).
Code:
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
vector<unordered_set<char>> rows(9), cols(9), boxes(9);
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char num = board[i][j];
if (num == '.') continue; // Skip empty cells
// Calculate the box index
int boxIndex = (i / 3) * 3 + (j / 3);
// Check if the number is already in the current row, column, or box
if (rows[i].count(num) || cols[j].count(num) || boxes[boxIndex].count(num)) {
return false;
}
// Add the number to the row, column, and box sets
rows[i].insert(num);
cols[j].insert(num);
boxes[boxIndex].insert(num);
}
}
return true;
}
};
Complexity Analysis:
- Time Complexity:
- We traverse the entire
9 x 9board once. For each cell, we perform constant time operations (checking and inserting into sets). Thus, the time complexity is O(9^2) = O(81) = O(1).
- We traverse the entire
- Space Complexity:
- We use three arrays of sets, each of size 9. Each set can hold up to 9 digits. Thus, the space complexity is O(9 * 9) = O(81) = O(1).
2️⃣ Optimal Approach
Approach:
We use three boolean arrays:
row[9][9]: Keeps track of whether a digit (1-9) has already appeared in each row.col[9][9]: Keeps track of whether a digit (1-9) has already appeared in each column.box[9][9]: Keeps track of whether a digit (1-9) has already appeared in each 3x3 sub-box.
For each cell in the 9x9 board:
- If the cell contains a
.(which represents an empty space), we skip it. - For any digit between '1' and '9', we convert it into a zero-based index (
digit = board[i][j] - '0' - 1). This gives us a number between 0 and 8. - We calculate the sub-box index using the formula:
boxIndex = (i / 3) * 3 + (j / 3). This formula maps each (i, j) coordinate to the appropriate sub-box (which are numbered from 0 to 8). - We check whether this digit has already been seen in the current row (
row[i][digit]), current column (col[j][digit]), or the current sub-box (box[boxIndex][digit]). If the digit has already appeared, the Sudoku board is invalid, so we returnfalse. - If the digit is valid and hasn’t been encountered before, we mark it as seen by setting
row[i][digit] = true,col[j][digit] = true, andbox[boxIndex][digit] = true.
If we successfully iterate through the entire board without finding any repeated digits, the board is valid, and we return true.
Steps:
- Initialize the data structures: We initialize three 9x9 boolean arrays (
row,col, andbox) tofalse, which will help us track whether each digit (1-9) has been encountered in the corresponding row, column, and sub-box. - Iterate through the board:
- For each cell
(i, j)in the 9x9 grid:- If the cell is empty (
.), skip it. - Otherwise, convert the character digit to a zero-based index.
- Calculate which 3x3 sub-box the current cell belongs to.
- Check if the digit already exists in the corresponding row, column, or sub-box.
- If it does, return
false. - Otherwise, mark the digit as present in the current row, column, and sub-box.
- If the cell is empty (
- For each cell
- Return the result: If all digits are valid (i.e., there are no duplicates in any row, column, or sub-box), return
true. Otherwise, returnfalse.
Dry Run:
Initialization:
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']
]
0 1 2 3 4 5 6 7 8
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
0 | 5 | 3 | . | . | 7 | . | . | . | . |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
1 | 6 | . | . | 1 | 9 | 5 | . | . | . |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
2 | . | 9 | 8 | . | . | . | . | 6 | . |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
3 | 8 | . | . | . | 6 | . | . | . | 3 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
4 | 4 | . | . | 8 | . | 3 | . | . | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
5 | 7 | . | . | . | 2 | . | . | . | 6 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
6 | . | 6 | . | . | . | . | 2 | 8 | . |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
7 | . | . | . | 4 | 1 | 9 | . | . | 5 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
8 | . | . | . | . | 8 | . | . | 7 | 9 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
row[9][9] = 0 1 2 3 4 5 6 7 8
+---+---+---+---+---+---+---+---+---+
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
col[9][9] = 0 1 2 3 4 5 6 7 8
+---+---+---+---+---+---+---+---+---+
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
box[9][9] = 0 1 2 3 4 5 6 7 8
+---+---+---+---+---+---+---+---+---+
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+First Iteration (i = 0, j = 0):
board =
0 1 2 3 4 5 6 7 8
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
0 | 5 | 3 | . | . | 7 | . | . | . | . |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
1 | 6 | . | . | 1 | 9 | 5 | . | . | . |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
2 | . | 9 | 8 | . | . | . | . | 6 | . |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
3 | 8 | . | . | . | 6 | . | . | . | 3 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
4 | 4 | . | . | 8 | . | 3 | . | . | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
5 | 7 | . | . | . | 2 | . | . | . | 6 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
6 | . | 6 | . | . | . | . | 2 | 8 | . |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
7 | . | . | . | 4 | 1 | 9 | . | . | 5 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
8 | . | . | . | . | 8 | . | . | 7 | 9 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
row[9][9] = 0 1 2 3 4 5 6 7 8
+---+---+---+---+---+---+---+---+---+
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
col[9][9] = 0 1 2 3 4 5 6 7 8
+---+---+---+---+---+---+---+---+---+
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
box[9][9] = 0 1 2 3 4 5 6 7 8
+---+---+---+---+---+---+---+---+---+
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
i = 0, j = 0, current cell is '5'
convert '5' to the index, digit = '5' - '0' - 1
= ASCII of 5 - ASCII of 0 - 1
= 53 - 48 - 1
= 5 - 1
= 4
calculate boxIndex = (i / 3) * 3 + (j / 3)
= (0/3)*3 + (0/3)
= 0
Since row[i][digit] = row[0][4] = false
col[i][digit] = col[0][4] = false
box[boxIndex][digit] = box[0][4] = false
We mark them as true.
Proceed to the next cell.Second Iteration (i = 0, j = 1):
board =
0 1 2 3 4 5 6 7 8
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
0 | 5 | 3 | . | . | 7 | . | . | . | . |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
1 | 6 | . | . | 1 | 9 | 5 | . | . | . |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
2 | . | 9 | 8 | . | . | . | . | 6 | . |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
3 | 8 | . | . | . | 6 | . | . | . | 3 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
4 | 4 | . | . | 8 | . | 3 | . | . | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
5 | 7 | . | . | . | 2 | . | . | . | 6 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
6 | . | 6 | . | . | . | . | 2 | 8 | . |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
7 | . | . | . | 4 | 1 | 9 | . | . | 5 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
8 | . | . | . | . | 8 | . | . | 7 | 9 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
row[9][9] = 0 1 2 3 4 5 6 7 8
+---+---+---+---+---+---+---+---+---+
0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
col[9][9] = 0 1 2 3 4 5 6 7 8
+---+---+---+---+---+---+---+---+---+
0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
box[9][9] = 0 1 2 3 4 5 6 7 8
+---+---+---+---+---+---+---+---+---+
0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
i = 0, j = 1, current cell is '3'
convert '3' to the index, digit = '3' - '0' - 1
= ASCII of 5 - ASCII of 0 - 1
= 51 - 48 - 1
= 3 - 1
= 2
calculate boxIndex = (i / 3) * 3 + (j / 3)
= (0/3)*3 + (1/3)
= 0 + 0
= 0
Since row[i][digit] = row[0][2] = false
col[i][digit] = col[0][2] = false
box[boxIndex][digit] = box[0][2] = false
We mark them as true.
Proceed to the next cell.Third Iteration (i = 0, j = 2):
board =
0 1 2 3 4 5 6 7 8
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
0 | 5 | 3 | . | . | 7 | . | . | . | . |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
1 | 6 | . | . | 1 | 9 | 5 | . | . | . |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
2 | . | 9 | 8 | . | . | . | . | 6 | . |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
3 | 8 | . | . | . | 6 | . | . | . | 3 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
4 | 4 | . | . | 8 | . | 3 | . | . | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
5 | 7 | . | . | . | 2 | . | . | . | 6 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
6 | . | 6 | . | . | . | . | 2 | 8 | . |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
7 | . | . | . | 4 | 1 | 9 | . | . | 5 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
8 | . | . | . | . | 8 | . | . | 7 | 9 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
row[9][9] = 0 1 2 3 4 5 6 7 8
+---+---+---+---+---+---+---+---+---+
0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
col[9][9] = 0 1 2 3 4 5 6 7 8
+---+---+---+---+---+---+---+---+---+
0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
box[9][9] = 0 1 2 3 4 5 6 7 8
+---+---+---+---+---+---+---+---+---+
0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+
i = 0, j = 2, current cell is '.' (empty)
Since it's empty, skip this cell and move to the next one.Keep doing this process for all the cells.
If any of the cell's value is already processed means set true in the flag array, return false.
Code:
class Solution {
public:
// Function to check if a given Sudoku board is valid.
bool isValidSudoku(vector<vector<char>>& board) {
// These boolean arrays will track the digits in rows, columns, and boxes respectively.
// Each element represents whether a digit (1 to 9) has been seen in that row, column, or box.
bool row[9][9] = {0}; // Tracks whether a digit is present in each row.
bool col[9][9] = {0}; // Tracks whether a digit is present in each column.
bool box[9][9] = {0}; // Tracks whether a digit is present in each 3x3 sub-box.
// Loop through each cell of the 9x9 board.
for(int i = 0; i < 9; i++) { // Iterate over rows.
for(int j = 0; j < 9; j++) { // Iterate over columns.
// If the current cell is empty ('.'), skip it.
if(board[i][j] == '.') continue;
// Convert the character digit to an integer index (0-based).
// board[i][j] is a character (e.g., '1' to '9'), and subtracting '0' gives its integer value.
// The -1 is used to make it zero-based for indexing purposes. For example, '1' becomes 0, '2' becomes 1, etc.
int digit = board[i][j] - '0' - 1;
// Calculate which 3x3 sub-box this cell belongs to.
// The sub-box indices are numbered as follows:
// [0] [1] [2]
// [3] [4] [5]
// [6] [7] [8]
// The formula (i/3)*3 + (j/3) gives the index of the sub-box based on the row (i) and column (j).
int boxIndex = (i/3) * 3 + (j/3);
// Check if this digit has already been seen in the current row, column, or sub-box.
// If it has, the board is invalid, so return false.
if(row[i][digit] || col[j][digit] || box[boxIndex][digit]) return false;
// Mark the digit as seen in the current row, column, and sub-box.
row[i][digit] = true;
col[j][digit] = true;
box[boxIndex][digit] = true;
}
}
// If all rows, columns, and boxes are valid, return true.
return true;
}
};
Complexity Analysis:
- Time Complexity:
O(1).- The algorithm iterates through each cell of a fixed 9x9 grid (i.e., 81 cells). For each cell, it performs constant-time operations like checking the boolean arrays and updating values.
- So, the time complexity is constant, O(1), since the grid size is fixed.
- Space Complexity:
O(1).- We use three fixed-size boolean arrays (
row,col, andbox), each with dimensions9x9. This results in a constant space usage since the size of these arrays does not grow with the input. Thus, the space complexity is also O(1).
- We use three fixed-size boolean arrays (