Check If Every Row and Column Contains All Numbers
Easy · Matrix · Array · Hash Table · Matrix
Problem
An n x n matrix is *valid* when every row and every column contains each integer from 1 to n exactly once.
Given an n x n integer matrix matrix, return true if it is valid, and false otherwise.
Examples
Input: matrix = [[2,3,1],[1,2,3],[3,1,2]] Output: True
Every row and every column is an arrangement of 1, 2, 3.
Input: matrix = [[1,2],[1,2]] Output: False
Column 0 holds 1 twice and no 2.
Input: matrix = [[1,1,3],[2,3,1],[3,2,2]] Output: False
Row 0 holds 1 twice and no 2.
Constraints
- n == len(matrix) == len(matrix[i])
- 1 <= n <= 100
- 1 <= matrix[i][j] <= n
Approaches
- Baseline: look for every number in every line — time O(n³), space O(1)
Follow-up
The range constraint does the heavy lifting: "contains every number" becomes "has no repeat". The use cases count the complete lines instead of checking all of them, and add the two diagonals.
Related problems
Start free on Cariara · Coding problems · System design studio
