algoadvance

Leetcode 2133. Check if Every Row and Column Contains All Numbers

Problem Statement

You are given an n x n integer matrix matrix. Return true if every row and every column contains all the integers from 1 to n (inclusive), otherwise return false.

Example

Example 1:

Input: matrix = [[1,2,3],[3,1,2],[2,3,1]]
Output: true
Explanation: In this case, n is 3, and every row and column contains the numbers 1, 2, and 3, which meets the requirement.

Example 2:

Input: matrix = [[1,1,1],[1,2,3],[1,2,3]]
Output: false
Explanation: In this case, n is 3, but the first row contains three 1s instead of the numbers 1, 2, and 3.

Clarifying Questions

To ensure full understanding of the problem, let’s clarify any possible confusion:

  1. Are all the numbers within the range from 1 to n in each row and column, or do we need to check for any kind of invalid values?
    • We only need to check for values between 1 and n in each row and column.
  2. Can n be 1, and if so, will a 1x1 matrix with value 1 be considered valid?
    • Yes, n can be 1, and a 1x1 matrix with value 1 should be considered valid.

Strategy

To solve this problem, we will:

  1. Iterate through each row and check if it contains all integers from 1 to n.
  2. Iterate through each column and check if it contains all integers from 1 to n.

We can utilize sets to check for the presence of each number efficiently.

Steps:

  1. Create a set of numbers from 1 to n.
  2. For each row, convert the row to a set and compare it with our number set.
  3. For each column, do the same by creating a set of values in the column and compare it with our number set.

Code

Here is the C++ solution for the problem:

#include <vector>
#include <unordered_set>

bool checkValid(std::vector<std::vector<int>>& matrix) {
    int n = matrix.size();
    std::unordered_set<int> expectedValues;
    
    for(int i = 1; i <= n; ++i) {
        expectedValues.insert(i);
    }
    
    // Check rows
    for(int i = 0; i < n; ++i) {
        std::unordered_set<int> rowValues(matrix[i].begin(), matrix[i].end());
        if(rowValues != expectedValues) {
            return false;
        }
    }
    
    // Check columns
    for(int j = 0; j < n; ++j) {
        std::unordered_set<int> colValues;
        for(int i = 0; i < n; ++i) {
            colValues.insert(matrix[i][j]);
        }
        if(colValues != expectedValues) {
            return false;
        }
    }
    
    return true;
}

Time Complexity

The time complexity is determined by the need to create sets for each row and each column, resulting in O(n^2):

Hence, the overall time complexity is O(n^2).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI