Scale Engineer

Check if Every Row and Column Contains All Numbers

Easy
#1943Time: O(n^2 log n) - We iterate through `n` rows and `n` columns. For each, we create a copy (O(n)) and sort it (O(n log n)). The total time is `n * O(n log n)` for rows and `n * O(n log n)` for columns, leading to an overall complexity of `O(n^2 log n)`.Space: O(n) - We need an auxiliary array of size `n` to hold the elements of a row or a column for sorting.3 companies
Data structures
ArrayHash TableMatrix
Companies
KaratIndeedInstacart

Prompt

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].length
  • 1 <= n <= 100
  • 1 <= matrix[i][j] <= n

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses sorting to validate each row and column. The core idea is that if a row or column contains all numbers from 1 to n exactly once, then after sorting, it must be identical to the sequence 1, 2, 3, ..., n. We can check this property for every row and every column.

Algorithm

  • Iterate through each row of the matrix from i = 0 to n-1.
  • For each row, create a temporary array and copy the row's elements into it.
  • Sort the temporary array.
  • After sorting, iterate through the temporary array. The element at index j should be j+1. If this condition is not met for any element, it means the row is invalid. Return false.
  • Repeat the same process for each column. Iterate from j = 0 to n-1.
  • For each column, create a temporary array and populate it with the column's elements.
  • Sort the column array and check if its elements are 1, 2, ..., n in order. If not, return false.
  • If all rows and columns pass the checks, the matrix is valid. Return true.

Walkthrough

We can break down the problem into two main parts: validating all rows and validating all columns.

For row validation, we iterate through each row. For a given row, we create a new array containing its elements. We then sort this new array. A valid row, when sorted, will have its elements in ascending order from 1 to n. So, we check if the element at index j of the sorted array is equal to j + 1. If we find any mismatch, we can immediately conclude the matrix is invalid and return false.

Similarly, for column validation, we iterate through each column. For each column, we create a temporary array and fill it with the elements from that column. We then sort this temporary array and perform the same check as we did for the rows. If any column is invalid, we return false.

If we successfully check all n rows and n columns without finding any issues, it means the matrix is valid, and we can return true.

import java.util.Arrays; class Solution {    public boolean checkValid(int[][] matrix) {        int n = matrix.length;         // Check each row        for (int i = 0; i < n; i++) {            int[] tempRow = new int[n];            for (int j = 0; j < n; j++) {                tempRow[j] = matrix[i][j];            }            Arrays.sort(tempRow);            for (int j = 0; j < n; j++) {                if (tempRow[j] != j + 1) {                    return false;                }            }        }         // Check each column        for (int j = 0; j < n; j++) {            int[] tempCol = new int[n];            for (int i = 0; i < n; i++) {                tempCol[i] = matrix[i][j];            }            Arrays.sort(tempCol);            for (int i = 0; i < n; i++) {                if (tempCol[i] != i + 1) {                    return false;                }            }        }         return true;    }}

Complexity

Time

O(n^2 log n) - We iterate through `n` rows and `n` columns. For each, we create a copy (O(n)) and sort it (O(n log n)). The total time is `n * O(n log n)` for rows and `n * O(n log n)` for columns, leading to an overall complexity of `O(n^2 log n)`.

Space

O(n) - We need an auxiliary array of size `n` to hold the elements of a row or a column for sorting.

Trade-offs

Pros

  • The logic is straightforward and easy to understand.

Cons

  • The time complexity of O(n^2 log n) is suboptimal for this problem.

  • Creating and sorting temporary arrays for each row and column is computationally expensive.

Solutions

class Solution {public  boolean checkValid(int[][] matrix) {    int n = matrix.length;    for (int i = 0; i < n; ++i) {      boolean[] seen = new boolean[n];      for (int j = 0; j < n; ++j) {        int v = matrix[i][j] - 1;        if (seen[v]) {          return false;        }        seen[v] = true;      }    }    for (int j = 0; j < n; ++j) {      boolean[] seen = new boolean[n];      for (int i = 0; i < n; ++i) {        int v = matrix[i][j] - 1;        if (seen[v]) {          return false;        }        seen[v] = true;      }    }    return true;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem