DSA
Valid Sudoku
Hashing & Sorting problem — solution with code and analysis.
Practice Here
Determine if a 9 x 9 Sudoku board is valid.
Hashing Approach#
A valid Sudoku board requires that each row, each column, and each 3×3 sub-box contains the digits 1–9 with no repeats. The approach makes three independent passes — one for rows, one for columns, and one for the nine 3×3 sub-boxes — using a 10-element boolean array as a presence set for each unit. If a digit is encountered a second time within any unit, the board is immediately invalid. This is O(81) = O(1) time since the board size is fixed, and O(10) = O(1) space per pass.
cpp
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
// check rows
for(int i=0;i<board.size();i++)
{
vector<bool> hash(10, false);
for(int j=0;j<board[i].size();j++)
{
char c = board[i][j];
if(c >= '0' && c<='9'){
if(hash[c-'0'])
return false;
hash[c-'0'] = true;
}
}
}
// check cols
for(int i=0;i<board.size();i++)
{
vector<bool> hash(10, false);
for(int j=0;j<board[i].size();j++)
{
char c = board[j][i];
if(c >= '0' && c<='9'){
if(hash[c-'0'])
return false;
hash[c-'0'] = true;
}
}
}
//check sub-boxes
for(int i=0;i<board.size();i+=3)
{
for(int j=0;j<board[i].size();j+=3)
{
vector<bool> hash(10, false);
for(int k=i;k<i+3;k++)
{
for(int l=j;l<j+3;l++)
{
char c = board[k][l];
if(c >= '0' && c<='9'){
if(hash[c-'0'])
return false;
hash[c-'0'] = true;
}
}
}
}
}
return true;
}
};