#2133

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Check if Every Row and Column Contains All Numbers

Determine if every row and column in a square matrix contains all numbers from 1 to n without repetition using array scanning and hash lookup.

array hash table matrix

Problem Statement

Given an n x n integer matrix, determine if it is valid. A valid matrix requires every row and every column to contain all integers from 1 to n exactly once. Return true if the matrix meets this condition, otherwise return false.

For example, matrix = [[1,2,3],[3,1,2],[2,3,1]] is valid because each row and column contains the numbers 1, 2, and 3. Matrix = [[1,1,1],[1,2,3],[1,2,3]] is invalid because the first row and first column do not contain all numbers from 1 to 3.

Examples

Example 1

Input: matrix = [[1,2,3],[3,1,2],[2,3,1]]

Output: true

In this case, n = 3, and every row and column contains the numbers 1, 2, and 3. Hence, we return true.

Example 2

Input: matrix = [[1,1,1],[1,2,3],[1,2,3]]

Output: false

In this case, n = 3, but the first row and the first column do not contain the numbers 2 or 3. Hence, we return false.

Constraints

n == matrix.length == matrix[i].length
1 <= n <= 100
1 <= matrix[i][j] <= n

Solution Approach

Row-wise scanning with hash set

Iterate through each row, inserting numbers into a hash set. If the set size is not equal to n or a duplicate appears, return false immediately. This pattern ensures fast detection of missing or repeated numbers per row.

Column-wise scanning with hash set

Repeat the same process for each column using a hash set. This ensures that each column also contains all numbers from 1 to n without duplicates, following the array scanning plus hash lookup pattern.

Combine results and return

If all rows and columns pass the hash set check, return true. This approach directly ties to the matrix validation pattern and avoids unnecessary full matrix reconstruction.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) because each of the n rows and n columns is scanned once. Space complexity is O(n) for the hash set used per row or column check.

What Interviewers Usually Probe

Check if the candidate efficiently uses a hash set for duplicate detection per row and column.
Observe whether they correctly iterate over both rows and columns without missing edge cases.
Listen for explanations about why this pattern avoids scanning the entire matrix multiple times unnecessarily.

Common Pitfalls or Variants

Common pitfalls

Failing to check both rows and columns can produce incorrect results even if rows are valid.
Using a single hash set for the entire matrix instead of per row/column can cause false positives.
Ignoring numbers outside the 1 to n range violates the problem constraints.

Follow-up variants

Check if the matrix is Latin square where numbers may start from 0 instead of 1.
Determine if only rows or only columns need to contain all numbers from 1 to n.
Validate larger sparse matrices efficiently using bit masks instead of hash sets.

FAQ

What is the most efficient way to check if every row and column contains all numbers?

Use a hash set per row and per column while scanning. If any set does not contain exactly n numbers, return false immediately.

Can I solve this problem without a hash set?

Yes, you can use an array of booleans or a bitmask for each row and column, but hash sets simplify handling duplicates and missing numbers.

What should I watch out for with this array scanning plus hash lookup pattern?

Ensure each row and column is checked separately. Using a shared set or skipping any column check may lead to incorrect validation.

Does the matrix size affect performance significantly?

Since the time complexity is O(n^2), matrices up to the constraint limit of n=100 are handled efficiently with this approach.

How does this pattern detect invalid matrices quickly?

Duplicates or missing numbers are caught immediately during scanning, allowing early return without scanning the remaining matrix.

terminal

Solution

Solution 1: Hash Table

Traverse each row and column of the matrix, using a hash table to record whether each number has appeared. If any number appears more than once in a row or column, return `false`; otherwise, return `true`

1

2

3

4

class Solution:
    def checkValid(self, matrix: List[List[int]]) -> bool:
        n = len(matrix)
        return all(len(set(row)) == n for row in chain(matrix, zip(*matrix)))

Continue Practicing

#2352 equal row and column pairs #2661 first completely painted row or column #2711 difference of number of distinct values on diagonals