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


  • 224

    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;
        }
    };

  • 11
    C

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


  • 0

    Oh, yes, that will save some memory space


  • 0
    H

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


  • 0

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


  • 0
    Y

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


  • 0
    J

    oh, i know....misunderstood


  • 0
    J

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


  • 0
    W

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


  • 2

    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;
        }
    }; 

  • 5

    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 :-)


  • 0
    N

    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?


  • 4
    F

    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

  • 0
    J

    thanks.it is clear!!!!


  • 0
    E

    k is computed in a really elegant way.


  • 0
    X

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


  • 0
    W

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


  • 0
    W
    This post is deleted!

  • 0
    E
    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

  • 0
    R

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


Log in to reply
 

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