Check If Every Row And Column Contains All Numbers - Leetcode Solution

Problem:

Given a rectangular integer matrix, determine if it is a "valid" Sudoku board. The Sudoku board is a 9x9 grid, which is divided into 9 3x3 sub-grids. Each cell in the grid contains an integer between 1 and 9, inclusive. The board is "valid" if:

1. Each row contains exactly one occurrence of each integer between 1 and 9, inclusive.
2. Each column contains exactly one occurrence of each integer between 1 and 9, inclusive.
3. Each sub-grid contains exactly one occurrence of each integer between 1 and 9, inclusive.

Solution:

To solve this problem, we need to check each row, each column, and each sub-grid to see if it contains all the numbers from 1 to 9. We can use a hash set to keep track of the numbers we have seen in each row, column, and sub-grid. If at any point we encounter a number that we have already seen in the hash set, we know that the Sudoku board is invalid.

To iterate over each row and column, we can use two nested for loops. To iterate over the sub-grids, we can use two additional nested loops to iterate over the rows and columns of each sub-grid.

At the end of each iteration, we need to clear the hash set so that we can start fresh for the next row, column, or sub-grid.

Here is the code to solve the problem:

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        unordered_set<char> seen;
        
        // Check rows
        for (int i = 0; i < 9; i++) {
            seen.clear();
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    if (seen.find(board[i][j]) != seen.end()) {
                        return false;
                    } else {
                        seen.insert(board[i][j]);
                    }
                }
            }
        }
        
        // Check columns
        for (int j = 0; j < 9; j++) {
            seen.clear();
            for (int i = 0; i < 9; i++) {
                if (board[i][j] != '.') {
                    if (seen.find(board[i][j]) != seen.end()) {
                        return false;
                    } else {
                        seen.insert(board[i][j]);
                    }
                }
            }
        }
        
        // Check sub-grids
        for (int i = 0; i < 9; i += 3) {
            for (int j = 0; j < 9; j += 3) {
                seen.clear();
                for (int k = 0; k < 3; k++) {
                    for (int l = 0; l < 3; l++) {
                        int row = i + k;
                        int col = j + l;
                        if (board[row][col] != '.') {
                            if (seen.find(board[row][col]) != seen.end()) {
                                return false;
                            } else {
                                seen.insert(board[row][col]);
                            }
                        }
                    }
                }
            }
        }
        
        return true;
    }
};

Time Complexity:

The time complexity of this solution is O(1) because the input matrix is always a 9x9 grid. Therefore, the nested loops run a constant number of times, and the time complexity of the algorithm is not dependent on the size of the input.

Space Complexity:

The space complexity of this solution is O(1) because we are using a hash set with a constant number of elements to keep track of the numbers that we have seen. Therefore, the space complexity of the algorithm is also not dependent on the size of the input.

1