https://leetcode.com/problems/valid-sudoku/description/

Approach 1: Hash Set

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int N = 9;
        unordered_set<char> rows[9];
        unordered_set<char> cols[9];
        unordered_set<char> boxes[9];

        for(int r = 0; r < N; r++){
            for(int c = 0; c < N; c++){
                char val = board[r][c];
                // Check if the position is filled with number
                if (val == '.'){
                    continue;
                }
                // Check the row
                if (rows[r].find(val) != rows[r].end()){
                    return false;
                }
                rows[r].insert(val);
                // Check the column
                if (cols[c].find(val) != cols[c].end()){
                    return false;
                }
                cols[c].insert(val);
                // Check the box
                int idx = (r/3) * 3 + c / 3;
                if (boxes[idx].find(val) != boxes[idx].end()){
                    return false;
                }
                boxes[idx].insert(val);
            }
        }
        return true;
    }
};

Complexity Analysis

Let $N$ be the board length, which is $9$ in this question. Note that since the value of $N$ is fixed, the time and space complexity of this algorithm can be interpreted as $O(1)$. However, to better compare each of the presented approaches, we will treat $N$ as an arbitrary value in the complexity analysis below.

• Time complexity: $O(N^2)$ because we need to traverse every position in the board, and each of the four check steps is an $O(1)$ operation.
• Space complexity: $O(N^2)$ because in the worst-case scenario, if the board is full, we need a hash set each with size $N$ to store all seen numbers for each of the $N$ rows, $N$ columns, and $N$ boxes, respectively.

Approach 2: Array of Fixed Length

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int N = 9;

        vector<vector<int>> rows(N, vector<int>(N,0));
        vector<vector<int>> cols(N, vector<int>(N,0));
        vector<vector<int>> boxes(N, vector<int>(N,0));
        for(int r = 0; r < N; r++){
            for(int c = 0; c < N; c++){
                // Check if the position is filled with number
                if(board[r][c] == '.'){
                    continue;
                }
                int pos = board[r][c] - '1';
                // Check the row
                if (rows[r][pos] == 1){
                    return false;
                }
                rows[r][pos] = 1;
                // Check the column
                if (cols[c][pos] == 1){
                    return false;
                }
                cols[c][pos] = 1;
                // Check the box
                int idx = (r/3) * 3 + c/3;
                if (boxes[idx][pos] == 1){
                    return false;
                }
                boxes[idx][pos] = 1;
            }
        }
        return true;
    }
};

Complexity Analysis

Let $N$ be the board length, which is $9$ in this question. Note that since the value of $N$ is fixed, the time and space complexity of this algorithm can be interpreted as $O(1)$. However, to better compare each of the presented approaches, we will treat $N$ as an arbitrary value in the complexity analysis below.

• Time complexity: $O(N^2)$ because we need to traverse every position in the board, and each of the four check steps is an $O(1)$ operation.
• Space complexity: $O(N^2)$ because we need to create $3N$ arrays each with size $N$ to store all previously seen numbers for all rows, columns, and boxes.

Approach 3: Bitmasking

// Char to int conversion in C++
// '0' gives actual face value (1-indexed):
int val = board[r][c] - '0';  // '1'->1, '2'->2, ... '9'->9

// '1' gives 0-indexed value:
int val = board[r][c] - '1';  // '1'->0, '2'->1, ... '9'->8

// Works because ASCII digit chars are consecutive:
// '0'=48, '1'=49, '2'=50 ... '9'=57
// so subtraction gives you the gap = face value

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        const int N = 9;
        // Use a binary number to record previous occurences
        int rows[N] = {0};
        int cols[N] = {0};
        int boxes[N] = {0};
        for(int r = 0; r < N; r++){
            for(int c = 0; c < N; c++){
                // Check if the position is filled with number
                if (board[r][c] == '.'){
                    continue;
                }
                int val = board[r][c] - '0';
                int pos = 1 << (val - 1);
                // Check the row
                if ((rows[r] & pos) > 0){
                    return false;
                }
                rows[r] |= pos;
                // Check the column
                if ((cols[c] & pos) > 0){
                    return false;
                }
                cols[c] |= pos;
                // Check the box
                int idx = (r/3) * 3 + c/3;
                if ((boxes[idx] & pos) > 0){
                    return false;
                }
                boxes[idx] |= pos;
            }
        }
        return true;

    }
};

Complexity Analysis

Let $N$ be the board length, which is $9$ in this question. Note that since the value of $N$ is fixed, the time and space complexity of this algorithm can be interpreted as $O(1)$. However, to better compare each of the presented approaches, we will treat $N$ as an arbitrary value in the complexity analysis below.

• Time complexity: $O(N^2)$ because we need to traverse every position in the board, and each of the four check steps is an $O(1)$ operation.
• Space complexity: $O(N)$ because in the worst-case scenario, if the board is full, we need $3N$ binary numbers to store all seen numbers in all rows, columns, and boxes. Using a binary number to record the occurrence of numbers is probably the most space-efficient method.