~/leetcode $ 36. Valid-Sudoku

We just want to check if the current sudoku board is valid or not. Therefore, we can just check that all integers in a row, column and 3x3 grid are all unique.

For the row and column, it is very straightforward - have a set for each of the row and if the integer is already in the set corresponding to that row/column, we can return false (the board is not valid).

We can do a similar thing for the 3x3 grid but through encoding 3x3 grid into a key (so that we can identify which grid corresponds to which set). For example, we can integer divide each row and column by 3 (so 0, 1, 2 becomes 0, 3, 4, 5 becomes 1, etc) and the corresponding (new_row, new_col) pair can be the grid identifier (e.g. (0, 0) corresponds to the top left grid). Because I don’t know how to use a tuple/pair as a key, I can use the following formula: key = (new_row * 3) + new_col which gives us a unique identifier for each grid.

Only problem with this solution is that uses a lot of space… 27 sets in total for each of the row, column and grids…

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        unordered_map<int, unordered_set<char>> rowVector {};
        unordered_map<int, unordered_set<char>> colVector {};
        unordered_map<int, unordered_set<char>> gridVector {};

        for (int row = 0; row < board.size(); ++row) {
            for (int col = 0; col < board[row].size(); ++col) {
                char currentChar = board[row][col];
                if (currentChar == '.') {
                    continue; // we don't care about blank spots
                }

                int new_row = row / 3;
                int new_col = col / 3;
                int gridIndex = (new_row * 3) + new_col;

                if (rowVector[row].contains(currentChar) || colVector[col].contains(currentChar) || gridVector[gridIndex].contains(currentChar)) {
                    return false;
                }

                rowVector[row].insert(currentChar);
                colVector[col].insert(currentChar);
                gridVector[gridIndex].insert(currentChar);
            }
        }

        return true;
    }
}

Note: after looking at some solutions, its way faster to just use a 9x9 array for each of the row, column, and grid with the first index corresponding to the row/col/grid and the second index corresponding to the number and the value is true/false - whether or not that number is in that row/col/grid or not (which makes sense since we know the problem space).

Time Complexity: O(n)

Space Complexity: O(n)

Time Taken: 7m 56s