Valid Sudoku
MedPrompt
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
- 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.
Note:
- A Sudoku board (partially filled) could be valid but is not necessarily solvable.
- Only the filled cells need to be validated according to the mentioned rules.
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: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.
Constraints:
board.length == 9board[i].length == 9board[i][j]is a digit1-9or'.'.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach improves upon the brute-force method by validating all rows, then all columns, and finally all 3x3 sub-boxes in separate phases. This avoids the redundant checks of the previous method.
Algorithm
- Validate Rows:
- For each row
ifrom 0 to 8:- Use a
HashSetto track seen digits. - Iterate through the row. If a digit is already in the set, return
false. Otherwise, add it.
- Use a
- For each row
- Validate Columns:
- For each column
jfrom 0 to 8:- Use a new
HashSet. - Iterate through the column. If a digit is already in the set, return
false. Otherwise, add it.
- Use a new
- For each column
- Validate Sub-boxes:
- For each of the 9 sub-boxes:
- Use a new
HashSet. - Iterate through the 3x3 cells of the box. If a digit is already in the set, return
false. Otherwise, add it.
- Use a new
- For each of the 9 sub-boxes:
- If all checks pass, return
true.
Walkthrough
The validation is split into three distinct parts:
- Row Validation: Iterate through each of the 9 rows. For each row, use a
HashSet(or a boolean array) to keep track of the digits encountered. If a digit is seen more than once in the same row, the board is invalid. - Column Validation: Similarly, iterate through each of the 9 columns. Use a fresh
HashSetfor each column to check for duplicate digits. - Sub-box Validation: Iterate through each of the 9 3x3 sub-boxes. A
HashSetis used for each sub-box to ensure no digit is repeated within it. The sub-boxes can be traversed by iterating their top-left corners, e.g.,(0,0), (0,3), (0,6), .... If all three validation phases complete successfully, the board is valid. This method processes each cell three times in total.
import java.util.HashSet;import java.util.Set; class Solution { public boolean isValidSudoku(char[][] board) { // Check rows for (int i = 0; i < 9; i++) { Set<Character> seen = new HashSet<>(); for (int j = 0; j < 9; j++) { char current = board[i][j]; if (current != '.') { if (seen.contains(current)) { return false; } seen.add(current); } } } // Check columns for (int j = 0; j < 9; j++) { Set<Character> seen = new HashSet<>(); for (int i = 0; i < 9; i++) { char current = board[i][j]; if (current != '.') { if (seen.contains(current)) { return false; } seen.add(current); } } } // Check 3x3 sub-boxes for (int boxRow = 0; boxRow < 3; boxRow++) { for (int boxCol = 0; boxCol < 3; boxCol++) { Set<Character> seen = new HashSet<>(); int startRow = boxRow * 3; int startCol = boxCol * 3; for (int i = startRow; i < startRow + 3; i++) { for (int j = startCol; j < startCol + 3; j++) { char current = board[i][j]; if (current != '.') { if (seen.contains(current)) { return false; } seen.add(current); } } } } } return true; }}Complexity
Time
O(N^2)
Space
O(N)
Trade-offs
Pros
Much more efficient than brute force with O(N^2) time complexity.
Code is well-structured and easy to follow.
Space efficient, using O(N) extra space.
Cons
Iterates over the board three times, which can be slightly less performant than a single-pass approach due to loop overhead and potentially worse cache performance.
This is the most efficient approach. It validates the board by iterating through each cell only once. It uses auxiliary data structures (arrays of HashSets) to keep track of the numbers seen in each row, column, and 3x3 sub-box simultaneously.
Algorithm
- Initialize three arrays of
HashSets:rows,cols, andboxes, each of size 9. - Iterate through the board from cell
(i, j) = (0,0)to(8,8). - For each cell that contains a digit
d:- Calculate the sub-box index:
box_index = (i / 3) * 3 + (j / 3). - Check if
dis already present inrows[i]. If so, returnfalse. - Check if
dis already present incols[j]. If so, returnfalse. - Check if
dis already present inboxes[box_index]. If so, returnfalse. - If no duplicates are found, add
dto all three sets:rows[i],cols[j], andboxes[box_index].
- Calculate the sub-box index:
- If the entire board is traversed without returning, the board is valid. Return
true.
Walkthrough
We declare three arrays of HashSets: rows[9], cols[9], and boxes[9]. The algorithm iterates through the board cell by cell from (0,0) to (8,8). For each cell (i, j) containing a digit d, it calculates the index of its sub-box using the formula box_index = (i / 3) * 3 + (j / 3). It then checks if d is already present in the corresponding sets for its row, column, and box. If a duplicate is found in any of them, the board is invalid. Otherwise, the digit is added to all three sets to be checked against subsequent cells. If the entire board is traversed without finding any duplicates, the function returns true.
import java.util.HashSet;import java.util.Set; class Solution { public boolean isValidSudoku(char[][] board) { Set<Character>[] rows = new HashSet[9]; Set<Character>[] cols = new HashSet[9]; Set<Character>[] boxes = new HashSet[9]; for (int i = 0; i < 9; i++) { rows[i] = new HashSet<>(); cols[i] = new HashSet<>(); boxes[i] = new HashSet<>(); } for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { char val = board[i][j]; if (val == '.') { continue; } // Check row if (rows[i].contains(val)) { return false; } rows[i].add(val); // Check column if (cols[j].contains(val)) { return false; } cols[j].add(val); // Check 3x3 box int boxIndex = (i / 3) * 3 + (j / 3); if (boxes[boxIndex].contains(val)) { return false; } boxes[boxIndex].add(val); } } return true; }}Complexity
Time
O(N^2)
Space
O(N^2)
Trade-offs
Pros
Most time-efficient as it traverses the board only once.
Elegant solution that combines all checks in a single loop.
Cons
Uses more space, O(N^2), compared to the grouped validation approach.
This approach iterates through every cell of the Sudoku board. For each cell that contains a number, it performs three separate checks: one for the row, one for the column, and one for the 3x3 sub-box to ensure there are no other occurrences of the same number.
Algorithm
- Iterate through each cell
(i, j)of the 9x9 board. - If the cell
board[i][j]contains a digit, store its value. - For the current cell's value, perform three separate validation checks:
- Row Check: Scan all other cells in the same row
ito see if the digit appears again. If a duplicate is found, returnfalse. - Column Check: Scan all other cells in the same column
jfor the same digit. If a duplicate is found, returnfalse. - Sub-box Check: Identify the 3x3 sub-box for cell
(i, j). Scan all other cells in this sub-box for the same digit. If a duplicate is found, returnfalse.
- Row Check: Scan all other cells in the same row
- If the loops complete without finding any duplicates for any cell, the board is valid. Return
true.
Walkthrough
The algorithm uses nested loops to traverse each cell (i, j) of the 9x9 board. If board[i][j] contains a digit, it's stored. Then, three validation checks are performed for this digit. If any of these checks find a duplicate, the board is invalid, and the function returns false. If the loops complete without finding any duplicates for any cell, the board is valid, and the function returns true. This method is straightforward but highly inefficient due to redundant comparisons. For example, the relationship between board[0][1] and board[0][2] will be checked when processing (0,1) and again when processing (0,2).
class Solution { public boolean isValidSudoku(char[][] board) { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (board[i][j] != '.') { if (!isValidPlacement(board, i, j)) { return false; } } } } return true; } private boolean isValidPlacement(char[][] board, int row, int col) { char val = board[row][col]; // Check row for duplicates for (int k = 0; k < 9; k++) { if (k != col && board[row][k] == val) { return false; } } // Check column for duplicates for (int k = 0; k < 9; k++) { if (k != row && board[k][col] == val) { return false; } } // Check 3x3 sub-box for duplicates int startRow = (row / 3) * 3; int startCol = (col / 3) * 3; for (int r = startRow; r < startRow + 3; r++) { for (int c = startCol; c < startCol + 3; c++) { if (r != row || c != col) { // Corrected condition if (board[r][c] == val) { return false; } } } } return true; }}Complexity
Time
O(N^3)
Space
O(1)
Trade-offs
Pros
Simple to understand and implement.
Uses constant extra space, O(1).
Cons
Highly inefficient due to a large number of redundant comparisons.
The time complexity is cubic with respect to the board size (N), making it unsuitable for larger boards.
Solutions
Solution
class Solution { public boolean isValidSudoku ( char [][] board ) { boolean [][] row = new boolean [ 9 ][ 9 ]; boolean [][] col = new boolean [ 9 ][ 9 ]; boolean [][] sub = new boolean [ 9 ][ 9 ]; for ( int i = 0 ; i < 9 ; ++ i ) { for ( int j = 0 ; j < 9 ; ++ j ) { char c = board [ i ][ j ]; if ( c == '.' ) { continue ; } int num = c - '0' - 1 ; int k = i / 3 * 3 + j / 3 ; if ( row [ i ][ num ] || col [ j ][ num ] || sub [ k ][ num ]) { return false ; } row [ i ][ num ] = true ; col [ j ][ num ] = true ; sub [ k ][ num ] = true ; } } return true ; } }/** * @param {character[][]} board * @return {boolean} */ var isValidSudoku = function (board) { const row = [...Array(9)].map(() => Array(9).fill(false)); const col = [...Array(9)].map(() => Array(9).fill(false)); const sub = [...Array(9)].map(() => Array(9).fill(false)); for (let i = 0; i < 9; ++i) { for (let j = 0; j < 9; ++j) { const num = board[i][j].charCodeAt() - " 1 ".charCodeAt(); if (num < 0 || num > 8) { continue; } const k = Math.floor(i / 3) * 3 + Math.floor(j / 3); if (row[i][num] || col[j][num] || sub[k][num]) { return false; } row[i][num] = true; col[j][num] = true; sub[k][num] = true; } } return true; };class Solution : def isValidSudoku ( self , board : List [ List [ str ]]) -> bool : row = [[ False ] * 9 for _ in range ( 9 )] col = [[ False ] * 9 for _ in range ( 9 )] sub = [[ False ] * 9 for _ in range ( 9 )] for i in range ( 9 ): for j in range ( 9 ): c = board [ i ][ j ] if c == '.' : continue num = int ( c ) - 1 k = i // 3 * 3 + j // 3 if row [ i ][ num ] or col [ j ][ num ] or sub [ k ][ num ]: return False row [ i ][ num ] = True col [ j ][ num ] = True sub [ k ][ num ] = True return Trueclass Solution { public: bool isValidSudoku ( vector < vector < char >>& board ) { vector < vector < bool >> row ( 9 , vector < bool > ( 9 , false )); vector < vector < bool >> col ( 9 , vector < bool > ( 9 , false )); vector < vector < bool >> sub ( 9 , vector < bool > ( 9 , false )); for ( int i = 0 ; i < 9 ; ++ i ) { for ( int j = 0 ; j < 9 ; ++ j ) { char c = board [ i ][ j ]; if ( c == '.' ) continue ; int num = c - '0' - 1 ; int k = i / 3 * 3 + j / 3 ; if ( row [ i ][ num ] || col [ j ][ num ] || sub [ k ][ num ]) { return false ; } row [ i ][ num ] = true ; col [ j ][ num ] = true ; sub [ k ][ num ] = true ; } } return true ; } };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.