Watch 10 video solutions for Check if Every Row and Column Contains All Numbers, a easy level problem involving Array, Hash Table, Matrix. This walkthrough by Coding Decoded has 2,416 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
An n x n matrix is valid if every row and every column contains all the integers from 1 to n (inclusive).
Given an n x n integer matrix matrix, return true if the matrix is valid. Otherwise, return false.
Example 1:
Input: matrix = [[1,2,3],[3,1,2],[2,3,1]] Output: true Explanation: 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 Explanation: 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].length1 <= n <= 1001 <= matrix[i][j] <= nProblem Overview: You are given an n x n matrix where values should range from 1 to n. The task is to verify that every row and every column contains all numbers from 1..n exactly once. If any row or column is missing a value or contains duplicates, the matrix is invalid.
Approach 1: Use Sets for Validation (Time: O(n2), Space: O(n))
This method uses a set to ensure uniqueness in each row and column. Iterate through the matrix row by row. For each row, insert elements into a set and verify that the set size becomes n while ensuring every value lies in the range 1..n. Repeat the same validation for every column. If any insertion encounters duplicates or invalid numbers, the matrix fails immediately. Set lookups and insertions are constant time on average, making the overall traversal O(n²).
This approach is intuitive and easy to implement. It relies on hash-based uniqueness checks, a common pattern when working with hash tables. Since each row and column requires its own temporary set, space usage stays at O(n). Most developers reach for this solution first because it is concise and hard to get wrong.
Approach 2: Use Count Arrays for Validation (Time: O(n2), Space: O(n))
Instead of hash sets, use a frequency array of size n + 1 for rows and columns. While iterating through a row, increment the count for matrix[i][j]. If the value is outside 1..n or its count exceeds 1, the row is invalid. Reset the array and repeat the process for each column. This approach replaces hashing with direct index access, which can be slightly faster and more memory predictable.
This pattern appears frequently in array and matrix validation problems where values fall within a known range. Since the value range is bounded by n, a counting structure becomes a natural fit.
Recommended for interviews: Both solutions run in O(n²) time, which is optimal because every cell must be inspected at least once. The set-based approach is typically preferred in interviews due to readability and fewer edge cases. The count-array version demonstrates deeper understanding of frequency tracking and constant-time indexing. Showing both approaches communicates strong problem-solving depth.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Use Sets for Validation | O(n²) | O(n) | Best general solution. Simple to implement with hash-based duplicate detection. |
| Use Count Arrays for Validation | O(n²) | O(n) | When values are guaranteed within 1..n and you want faster constant-time indexing without hashing. |