algoadvance

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

Problem Statement

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`.

Clarifying Questions

1. Can we assume the matrix only contains integers?
   • Yes, the problem implies that the matrix contains integers.
2. What are the constraints on n?
   • The problem does not specify constraints explicitly, but a typical assumption for such problems is that n can vary from small sizes like 1 to larger sizes in the range of hundreds.
3. Can there be duplicate values in the rows or columns?
   • The problem implies that each row and column should contain all numbers from 1 to n without duplicates.
4. Will the matrix always be square?
   • Yes, since the problem is for an n x n matrix, it will always be square.

Strategy

To solve this problem, we need to validate two conditions for an n x n matrix:

1. Every row contains all numbers from 1 to n.
2. Every column contains all numbers from 1 to n.

To achieve this:

1. We can use two sets of size n for each row and column to track the numbers.
2. For each row and column, we iterate through their elements and add them to the respective set.
3. After iterating through a row or column, we check if the set contains exactly the numbers [1, 2, ..., n].

Code

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public boolean checkValid(int[][] matrix) {
        int n = matrix.length;
        
        for (int i = 0; i < n; i++) {
            Set<Integer> rowSet = new HashSet<>();
            Set<Integer> colSet = new HashSet<>();
            for (int j = 0; j < n; j++) {
                rowSet.add(matrix[i][j]);
                colSet.add(matrix[j][i]);
            }
            for (int num = 1; num <= n; num++) {
                if (!rowSet.contains(num) || !colSet.contains(num)) {
                    return false;
                }
            }
        }
        return true;
    }
}

Time Complexity

• Outer Loop (Rows): The outer loop runs n times.
• Inner Loop (Columns): The inner loops run n times.
• Set Operations: Adding elements and checking conditions is approximately O(1) for sets of size up to n (due to the hashing mechanism).

Overall, the time complexity is O(n^2) because we iterate over the entire matrix with nested loops.

Space Complexity

• Sets for Rows and Columns: We use 2 sets for each row and column, each of at most size n.
• Thus, the space complexity is O(n) in terms of additional space.

In summary, the solution uses an efficient approach leveraging sets to ensure each row and column in the matrix contains all integers from 1 to n. The time complexity is O(n^2) which is optimal for this type of problem.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?