36. Valid Sudoku

Solution - Use Three Vectors

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board)
    {
        int n = 9;
        vector<vector<int>> rows_seen(n, vector<int>(n));
        vector<vector<int>> cols_seen(n, vector<int>(n));
        vector<vector<int>> boxes_seen(n, vector<int>(n));
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(board[i][j] == '.') continue;

                int c = board[i][j] - '1';

                int boxIndex = 3 * (i / 3) + j / 3;

                if (rows_seen[i][c] || cols_seen[c][j] || boxes_seen[boxIndex][c])
                    return false;

                rows_seen[i][c] = 1;
                cols_seen[c][j] = 1;
                boxes_seen[boxIndex][c] = 1;
            }
        }
        return true;
    }
};

• T:
  $O(N^2)$
• S:
  $O(N^2)$

Solution - Use Three HashSet

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board)
    {
        unordered_set<int> rowSet[9], colSet[9], boxSet[9];
        for (int i = 0; i < 9; ++i)
        {
            for (int j = 0; j < 9; ++j)
            {
                char val = board[i][j];

                if (val == '.') continue;

                if (rowSet[i].count(val)) return false;
                rowSet[i].insert(val);

                if (colSet[j].count(val)) return false;
                colSet[j].insert(val);

                int boxIndex = (i / 3) * 3 + j / 3;
                if (boxSet[boxIndex].count(val)) return false;
                boxSet[boxIndex].insert(val);
            }
        }
        return true;
    }
};

• T:
  $O(N^2)$
• S:
  $O(N^2)$

Solution - Use One HashSet

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board)
    {
        int n = 9;
        unordered_set<string> st;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (board[i][j] == '.') continue;
                string t = "(" + to_string(board[i][j] - '0') + ")";
                string row = to_string(i) + t;
                string col = t + to_string(j);
                string cell = to_string(i / 3) + t + to_string(j / 3);
                if (st.count(row) || st.count(col) || st.count(cell)) return false;
                st.insert(row);
                st.insert(col);
                st.insert(cell);
            }
        }
        return true;        
    }
};

• T:
  $O(N^2)$
• S:
  $O(N)$