Valid Sudoku: Using Indices as Hash Tables
Valid Sudoku: Using Indices as Hash Tables
Special traversal technique. Use indices as simple hash tables.
Time: O(N²)
bool isValidSudoku(vector<vector<char>>& board) {
int used1[9][10] = {0};
int used2[9][10] = {0};
int used3[9][10] = {0};
for(int i=0;i<9;++i) {
for(int j=0;j<9;++j) {
if (board[i][j]!='.') {
int num=board[i][j]-'0';
int k=(i/3)*3+j/3;
if (used1[i][num]||used2[j][num]||used3[k][num])
return false;
used1[i][num]=used2[j][num]=used3[k][num]=1;
}
}
}
return true;
}The code tracks three constraints: rows, columns, and 3x3 boxes. Each used array handles one type. The index serves as the key - no need for actual hash functions. This keeps the solution fast and simple.
#array