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] <= nIn this problem, you are given an n x n matrix where each value should ideally range from 1 to n. The task is to verify whether every row and every column contains all numbers from 1 to n exactly once. This essentially checks if each row and column forms a valid permutation of the range.
A common approach is to iterate through each row and column while using a hash set or a boolean frequency array to track which numbers appear. For each row, insert elements into the set and ensure its size becomes n. Repeat the same validation for each column. If any duplicate appears or a number outside the valid range exists, the matrix is invalid.
This method works efficiently because each cell is inspected a constant number of times. The overall time complexity is O(n²) since the matrix must be fully traversed, while the space complexity is O(n) due to the temporary set or frequency structure used for validation.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Row and Column Validation using Hash Set / Boolean Array | O(n^2) | O(n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Use for loops to check each row for every number from 1 to n. Similarly, do the same for each column.
For each check, you can keep a set of the unique elements in the checked row/col. By the end of the check, the size of the set should be n.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Even if all rows contain numbers from 1 to n, columns may still contain duplicates or missing values. Verifying both ensures the matrix satisfies the problem's condition completely.
Yes, variations of matrix validation problems are common in coding interviews. They test a candidate’s understanding of arrays, hashing, and matrix traversal patterns in a simple but structured way.
A hash set or a boolean frequency array works best for tracking whether numbers from 1 to n appear exactly once. These structures allow constant-time checks for duplicates and missing values while scanning rows and columns.
The optimal approach is to iterate through each row and column while tracking seen values using a hash set or boolean array. If each row and column contains exactly the numbers from 1 to n without duplicates, the matrix is valid. This method runs in O(n^2) time.