# My C++ code (O(n2) time and space)

• The basic idea is to use an array to indicate whether a number in a row/column/3x3 sub-block already occurs. We need a 9x9 array existNum and
a) the LSB of existNum[i][j] indicates whether number j occurs on the i-th row before
b) the 2-LSB of existNum[i][j] indicates whether number j occurs on the i-th column before
c) the 3-LSB of existNum[i][j] indicates whether number j occurs on the i-th sub-block before, k= (i/3)*3 + j/3

``````class Solution {
public:
bool isValidSudoku(vector<vector<char> > &board) {
char existNum[10][10]={0};
int i,j;

for(i=0; i<9; i++)
{
for(j=0; j<9; j++)
{
if(board[i][j]!='.')
{
if(existNum[i][board[i][j] - '0'] & 0x1)return false; // check if the i-row already has such number, LSB
if(existNum[j][board[i][j] - '0'] & 0x2) return false; // check if the j-col already has such number, 2-LSB
if(existNum[(i/3) *3 + j/3][board[i][j] - '0'] & 0x4) return false; // check if the k-subblock already has such number, 3-LSB
existNum[i][board[i][j] - '0'] ^=0x1;
existNum[j][board[i][j] - '0'] ^=0x2;
existNum[(i/3) *3 + j/3][board[i][j] - '0'] ^=0x4;
}

}
}

return true;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.