Interview Question for Software Engineer at Google:

I use two loop to do the judgement and the time complexity is O(n^2)

It can be done in O(n) really easy :).

you need 27 variables (int). And based on the coordinates in the sudoku table you update for each value 3 of these by setting the corresponding bit to 1.

At the end in order to check the validity of the solution, it just needs all those 27 variables to be 111111111(2). If not, then you have no solution!

Implementing is straightforward!

@Interview Candidate , I don't think your solution is correct, because there is a nother requirment which is that every 3X3 part is also 1-9, so the complexity becomes n^3.

@Gabriel, I don't understand your solution, can you make it clearer?

@Gabriel, but you still need to scan the board, right? That's still O(n^2) IMHO.

I think it's actually O(3*9) time plus O(9) space, count sorting each row, column and 3x3 square. If even one of the integer in each row, column or square is counted twice you can just return false. If the counts succeed in all three cases then return true.

By the way, if the sudoku is not 3 * 3 based, but k * k, then you have O(3 * k * k) time (count sorting each row, column and square) and O(k * k) space.