Leetcode 2133. Check if Every Row and Column Contains All Numbers
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`.
n
?
n
can vary from small sizes like 1
to larger sizes in the range of hundreds.1
to n
without duplicates.n x n
matrix, it will always be square.To solve this problem, we need to validate two conditions for an n x n
matrix:
1
to n
.1
to n
.To achieve this:
n
for each row and column to track the numbers.[1, 2, ..., n]
.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;
}
}
n
times.n
times.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.
n
.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.
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?