# Check if Every Row and Column Contains All Numbers
**Difficulty:** EASY
[External](https://leetcode.com/problems/check-if-every-row-and-column-contains-all-numbers)
Canonical: https://scaleengineer.com/dsa/problems/check-if-every-row-and-column-contains-all-numbers
**Data structures:** Array, Hash Table, Matrix
**Companies:** [Karat](https://scaleengineer.com/companies/karat), [Indeed](https://scaleengineer.com/companies/indeed), [Instacart](https://scaleengineer.com/companies/instacart)
---
## Problem
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:**

![](https://assets.glich.co/dsa/check-if-every-row-and-column-contains-all-numbers/image0.png) 

**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:**

![](https://assets.glich.co/dsa/check-if-every-row-and-column-contains-all-numbers/image1.png) 

**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
## Brute Force using Sorting
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.
**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.
**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.
### Explanation
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`.

```java
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;
    }
}
```
### 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`.

## Using Hash Sets for Duplicate Checking
A more efficient approach is to use a hash set to check for the uniqueness of elements in each row and column. The problem states that all numbers are between 1 and `n`. Therefore, if a row or column of size `n` contains `n` unique numbers, it must contain all numbers from 1 to `n`.

We can iterate through each row, add its elements to a hash set, and then check if the set's size is `n`. We do the same for each column. If any check fails, the matrix is invalid.
**Time:** O(n^2) - We traverse the `n x n` matrix twice. Once for rows (`n` rows * `n` elements = `O(n^2)`) and once for columns (`n` columns * `n` elements = `O(n^2)`). The total time is `O(n^2) + O(n^2) = O(n^2)`. · **Space:** O(n) - For each row or column check, a `HashSet` is created which can store up to `n` elements.
**Pros:** Time complexity of `O(n^2)` is a significant improvement over the sorting approach.; The logic is still relatively easy to follow.
**Cons:** Requires two separate passes over the matrix data (one for rows, one for columns).; Using a `HashSet` has more overhead (both in memory and time) compared to a simple boolean array, although the asymptotic complexity is the same.
### Explanation
This method leverages the properties of a `HashSet`, which only stores unique elements. The validation process is again split into checking rows and columns separately.

To check the rows, we loop from `i = 0` to `n-1`. In each iteration, we initialize a new `HashSet`. We then traverse the `i`-th row, adding each element `matrix[i][j]` to the set. Since a set automatically handles duplicates (i.e., adding an existing element does nothing), we can determine if the row is valid by its final state. After iterating through all elements in the row, if the `size()` of the set is less than `n`, it means there was at least one duplicate number, and the row is not a valid permutation of `1...n`. In this case, we return `false`.

We apply the exact same logic to the columns. We loop from `j = 0` to `n-1`, create a new `HashSet` for each column, populate it with the column's elements, and check if its final size is `n`. If any column fails this test, we return `false`.

If all `2n` checks (for `n` rows and `n` columns) pass, the matrix is valid, and we return `true`.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean checkValid(int[][] matrix) {
        int n = matrix.length;

        // Check each row
        for (int i = 0; i < n; i++) {
            Set<Integer> rowSet = new HashSet<>();
            for (int j = 0; j < n; j++) {
                rowSet.add(matrix[i][j]);
            }
            if (rowSet.size() != n) {
                return false;
            }
        }

        // Check each column
        for (int j = 0; j < n; j++) {
            Set<Integer> colSet = new HashSet<>();
            for (int i = 0; i < n; i++) {
                colSet.add(matrix[i][j]);
            }
            if (colSet.size() != n) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
- Iterate through each row of the matrix from `i = 0` to `n-1`.
- For each row, create an empty `HashSet`.
- Iterate through the elements of the current row and add each element to the set.
- After processing the row, check if the size of the set is equal to `n`. If not, it implies there were duplicate numbers, so the row is invalid. Return `false`.
- Repeat the same process for each column. Iterate from `j = 0` to `n-1`.
- For each column, use a `HashSet` to collect its elements.
- If the set's size is not `n` for any column, return `false`.
- If all rows and columns are validated, return `true`.

## Optimized Single Pass with Boolean Arrays
This is the most optimized approach. We can improve on the previous method by combining the row and column checks into a single pass and by using a boolean array instead of a `HashSet`. Since the numbers are constrained to be within `[1, n]`, a boolean array of size `n+1` can serve as a direct-access hash set, which is faster and more memory-efficient.

In a single main loop, we can validate the `i`-th row and the `i`-th column at the same time. This reduces code duplication and can have minor performance benefits due to better data locality.
**Time:** O(n^2) - We have a nested loop structure where the outer loop runs `n` times and the inner loop runs `n` times. All operations inside the loops are constant time. Thus, the total time complexity is `O(n*n) = O(n^2)`. · **Space:** O(n) - In each iteration of the outer loop, we create two boolean arrays of size `n+1`. The space is reused in each iteration, so the peak space complexity is `O(n)`.
**Pros:** Most efficient approach with `O(n^2)` time complexity.; Uses boolean arrays which are faster and more memory-efficient than hash sets.; Combines row and column checks into a single, elegant loop structure.
**Cons:** The logic of checking row `i` and column `i` in the same outer loop iteration can be slightly less intuitive than checking all rows then all columns.
### Explanation
The key optimization here is to perform all checks within a single `O(n^2)` traversal of the matrix's indices. We can iterate from `i = 0` to `n-1`, and in each iteration, we focus on validating both row `i` and column `i`.

For each `i`, we declare two boolean arrays, `rowCheck` and `colCheck`, of size `n+1`, initialized to `false`. These arrays will track which numbers we've seen in the current row and column, respectively. The index of the array corresponds to the number (e.g., `rowCheck[5]` corresponds to the number 5).

We then use a nested loop with index `j` from `0` to `n-1`. Inside this loop, we perform two checks:
1.  **Row Check**: We look at the element `matrix[i][j]`. If `rowCheck[matrix[i][j]]` is already `true`, it means we've seen this number before in the current row, indicating a duplicate. We immediately return `false`.
2.  **Column Check**: We look at the element `matrix[j][i]`. If `colCheck[matrix[j][i]]` is `true`, we've found a duplicate in the current column and return `false`.

If the numbers are not duplicates, we mark them as seen by setting `rowCheck[matrix[i][j]] = true` and `colCheck[matrix[j][i]] = true`.

By the time the inner `j` loop finishes, we have fully validated row `i` and column `i`. The outer `i` loop ensures that every row and every column is eventually checked. If the entire process completes without returning `false`, the matrix is valid.

```java
class Solution {
    public boolean checkValid(int[][] matrix) {
        int n = matrix.length;

        for (int i = 0; i < n; i++) {
            boolean[] rowCheck = new boolean[n + 1];
            boolean[] colCheck = new boolean[n + 1];

            for (int j = 0; j < n; j++) {
                // Check for duplicates in row i
                int rowVal = matrix[i][j];
                if (rowCheck[rowVal]) {
                    return false;
                }
                rowCheck[rowVal] = true;

                // Check for duplicates in column i
                int colVal = matrix[j][i];
                if (colCheck[colVal]) {
                    return false;
                }
                colCheck[colVal] = true;
            }
        }

        return true;
    }
}
```
### Algorithm
- Get the size of the matrix, `n`.
- Start a single loop that iterates from `i = 0` to `n-1`. This loop will handle the validation of the `i`-th row and the `i`-th column simultaneously.
- Inside this loop, create two boolean arrays, `rowCheck` and `colCheck`, each of size `n+1`. These will act as frequency maps.
- Start a nested loop that iterates from `j = 0` to `n-1`.
- In the inner loop, check the `i`-th row: let `rowVal = matrix[i][j]`. If `rowCheck[rowVal]` is already `true`, we have found a duplicate in the row. Return `false`.
- Mark the number as seen for the current row: `rowCheck[rowVal] = true`.
- Simultaneously, check the `i`-th column: let `colVal = matrix[j][i]`. If `colCheck[colVal]` is already `true`, we have found a duplicate in the column. Return `false`.
- Mark the number as seen for the current column: `colCheck[colVal] = true`.
- If the outer loop completes without returning `false`, it means every row and every column has been validated successfully. Return `true`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool checkValid(vector<vector<int>> &matrix) {
    int n = matrix.size();
    for (int i = 0; i < n; ++i) {
      vector<bool> seen(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) {
      vector<bool> seen(n);
      for (int i = 0; i < n; ++i) {
        int v = matrix[i][j] - 1;
        if (seen[v])
          return false;
        seen[v] = true;
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def checkValid(self, matrix: List[List[int]]) -> bool: n = len(matrix) for i in range(n): seen = [False] * n for j in range(n): v = matrix[i][j] - 1 if seen[v]: return False seen[v] = True for j in range(n): seen = [False] * n for i in range(n): v = matrix[i][j] - 1 if seen[v]: return False seen[v] = True return True

```