My short solution by C++. O(n2)

• Three flags are used to check whether a number appear.

used1: check each row

used2: check each column

used3: check each sub-boxes

``````class Solution
{
public:
bool isValidSudoku(vector<vector<char> > &board)
{
int used1[9][9] = {0}, used2[9][9] = {0}, used3[9][9] = {0};

for(int i = 0; i < board.size(); ++ i)
for(int j = 0; j < board[i].size(); ++ j)
if(board[i][j] != '.')
{
int num = board[i][j] - '0' - 1, 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;
}
};``````

• Nice and elegant! I would only change used[][] arrays to bool.

• Oh, yes, that will save some memory space

• Should not this code be O(N)? You scaned each grid only once.

• I mean that the board is n*n. So it is O(n2). Certainly I scan each grid only once.

• I was really surprised that my code is nearly the same as yours except mine is in C, elegant , thank you.

• oh, i know....misunderstood

• i tried to change int to bool,and change 1 to true,but it doesn't work.i don't know the reason...

• assignment in C or C++ returns value that why I hate it. Complier won't tell you anything about if(x=1)

• Hi, jppjpr. The following code using `bool` instead of `int` gets accepted :-) In fact, at first I made a mistake by forgetting to check `if (board[i][j] != '.')`.

``````class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
bool row[9][9] = {false}, col[9][9] = {false}, box[9][9] = {false};
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
int num = board[i][j] - '0' - 1, k = i / 3 * 3 + j / 3;
if (row[i][num] || col[j][num] || box[k][num]) return false;
row[i][num] = col[j][num] = box[k][num] = true;
}
}
}
return true;
}
}; ``````

• Great code! I really love this line

``````int num = board[i][j] - '0' - 1, k = i / 3 * 3 + j / 3;
``````

The variable `k` so nicely maps all the cells belonging to the same box to the same element of `used3` :-)

• Great solution! One quick comment - I tried to generalize the used array for the board size by:
used1[9][9] --> used1[board.size()][board.size()] but it failed the tests... anybody know why?
I did verify that board.size() == 9 for this problem.. any idea why this happens?

• Cool! Python version:

``````def isValidSudoku(self,board):
if not board:return False
m,n=len(board),len(board[0])
check_row=[[0 for i in range(9)] for j in range(9)]#three 2d array to check each row, col and sub box
check_col=[[0 for i in range(9)] for j in range(9)]#three 2d array to check each row, col and sub box
check_box=[[0 for i in range(9)] for j in range(9)]#three 2d array to check each row, col and sub box
for i in xrange(m):
for j in xrange(n):
if board[i][j] != '.':
num=int(board[i][j])-1 # need -1 becasue the index of array is 0~8
k=i/3*3+j/3
#because if previously the same number of same row,col or box have exist, it is false
if check_row[i][num] or check_col[j][num] or check_box[k][num]:
return False
#assign value to all the checking 2d arrayes

check_row[i][num]=check_col[j][num]= check_box[k][num]=1
return True``````

• thanks.it is clear!!!!

• k is computed in a really elegant way.

• why num = board[i][j] - '0' - 1? , k = i / 3 * 3 + j / 3

• board.size() is determined at runtime. and used1[9][9] at compile time

• This post is deleted!

1. num should be in the range of [0, 8] instead of [1, 9] to be mapped in to row[9][9];
2. for mapping num into sub-boxes

• its daring task to choose so much space ,, although appreciated.

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