A concise O(N^2) solution


  • 0
    S
    bool isValidSudoku(vector<vector<char> > &board) {
         vector<vector<int>> bucket;
         for (int i = 0; i < 9; i++) {
             // each time check one horizon, one verticality and one box
             bucket = vector<vector<int>>(3, vector<int>(9, 0));
             for (int j = 0; j < 9; j++) {
                 // horizontal 
                 if (board[i][j] != '.' && ++bucket[0][board[i][j] - '1'] > 1) return false;
                 // vertical 
                 if (board[j][i] != '.' && ++bucket[1][board[j][i] - '1'] > 1) return false;
                 // boxical
                 int h = j/3 + 3*(i/3), v = j%3 + 3*(i%3);
                 if (board[h][v] != '.' && ++bucket[2][board[h][v] - '1'] > 1) return false;
             }
         }
    }

  • 0
    S

    Don't you think it's always O(1).


Log in to reply
 

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