2133. Check if Every Row and Column Contains All Numbers

EasyArrayHash TableMatrix
Leetcode Link

Problem Description

In this problem, we are given an n x n integer matrix and we need to determine if this matrix is "valid". A matrix is considered valid if every row and every column contains all the integers from 1 to n (inclusive). This essentially means that, in a valid matrix, each number in the range from 1 to n should appear exactly once in each row and exactly once in each column without any repetition or omission. The function should return true if the matrix is valid, and false otherwise.

Intuition

To determine if the given matrix is valid, we need to verify two conditions for each number from 1 to n:

  1. It appears exactly once in each row.
  2. It appears exactly once in each column.

Since we need to check all numbers against both rows and columns, we can tackle each one independently. Here's the intuition behind our approach:

  • For checking rows, we iterate over each row and create an array seen of size n where each element is initially set to False. As we encounter a number in a row, we calculate its index in the seen array by subtracting 1. If the corresponding index in the seen array is already True, it means we have seen this number earlier in this row, which violates our condition, so we return False. If not, we set the corresponding index to True.

  • For checking columns, we repeat the same process but iterate column-wise instead of row-wise, hence we'll have separate iterations for rows and columns.

  • If both row-wise and column-wise iterations do not return False, it means that the matrix satisfies the condition of having unique numbers from 1 to n in all rows and columns, and thus, we return True, confirming that the matrix is valid.

Solution Approach

The implementation of the solution uses a straightforward approach to verify the conditions for a valid matrix. The checkValid function is called with the matrix as input, and it is intended to return a boolean value indicating the validity of the matrix. Here's a step-by-step explanation of the solution approach:

  1. We determine the size of the matrix n by getting the length of the matrix, which is represented as the number of rows (or columns since it is n x n).

  2. The function has two nested loops for each condition, i.e., one set for checking the rows and another for checking the columns:

    • For rows:
      • We iterate over each row with index i.
      • Inside this loop, we initialize an array seen of size n with all values set to False. This array keeps track of the numbers we have come across in the current row.
      • We then iterate over each element of the row with index j.
      • We calculate the value v by subtracting 1 from the matrix element matrix[i][j], which effectively translates the value to an index that corresponds to the range [0, n-1].
      • If seen[v] is True, it means the number v+1 was previously encountered in the same row, thus we should return False as the row does not contain unique numbers.
      • If seen[v] is False, we mark it True, indicating that we've encountered v+1 for the first time in the current row.
    • For columns:
      • The process is similar to rows but we iterate over each column with index j first.
      • For each column, we initialize a fresh seen array, and then iterate over each row i.
      • We use the same logic as we did for rows to mark off seen values for the column elements.
  3. If we successfully exit both nested loops without returning False, it means the matrix has passed all validation checks and we return True.

The algorithm uses an array-based implementation and checks for the presence of numbers using a boolean array. The time complexity of this algorithm is O(n^2) since we have to check every element of an n x n matrix twice, once for row-wise and once for column-wise uniqueness.

Example Walkthrough

Let's walk through an example to understand how the solution approach works. We will use a 3 x 3 matrix for this example to illustrate the validation process.

Consider the following matrix:

1 [[1, 2, 3],
2  [2, 3, 1],
3  [3, 1, 2]]

We need to determine if this matrix is valid according to the specified conditions. The conditions are that the numbers 1 to n should appear exactly once in each row and once in each column.

Step 1: Initialization

First, we identify n, the size of the matrix, which is 3.

Step 2: Check Rows for Uniqueness

We initialize a seen array for the first row and set all its values to False [False, False, False].

  • We look at the first element of the first row, which is 1. Subtract 1 to get the index 0. We update the seen array at index 0 to True to indicate that 1 has been seen: [True, False, False].
  • Next, we see the number 2. Subtract 1 to get the index 1. Update the seen array at index 1 to True to indicate that 2 has been seen: [True, True, False].
  • Lastly, we look at 3. We subtract 1 to get the index 2 and update seen at index 2 to True, indicating that 3 has been seen: [True, True, True].

Since we do not encounter any True value during this process, this row passes the uniqueness check.

We repeat this process for the second and third rows and in both cases, we don’t find any duplicates.

Step 3: Check Columns for Uniqueness

We would then perform a similar check column-wise.

  • For the first column with values [1, 2, 3], we set a seen array as [False, False, False]. As we iterate through the column and mark each number as seen, our seen array becomes [True, True, True].
  • We do the same for the second and third columns, and in both cases, we find that each number from 1 to 3 appears only once.

Once both row-wise and column-wise checks are complete without encountering any True value in seen for already encountered elements, we can conclude that this matrix is indeed valid, and the function would return True.

Following the solution approach, our final output for the provided matrix [1, 2, 3], [2, 3, 1], [3, 1, 2] would be True, signaling that the matrix satisfies the required conditions of validity.

Python Solution

1class Solution:
2    def checkValid(self, matrix: List[List[int]]) -> bool:
3        # Find the size of the matrix
4        size = len(matrix)
5
6        # Check every row in the matrix
7        for row in range(size):
8            # Initialize a list to keep track of seen numbers in the current row
9            seen_row = [False] * size
10            for col in range(size):
11                # Calculate the correct index for the value considering 1-based to 0-based indexing
12                value_index = matrix[row][col] - 1
13              
14                # If we have already seen this number in the current row, the matrix is not valid
15                if seen_row[value_index]:
16                    return False
17              
18                # Mark the number as seen in the current row
19                seen_row[value_index] = True
20
21        # Check every column in the matrix
22        for col in range(size):
23            # Initialize a list to keep track of seen numbers in the current column
24            seen_col = [False] * size
25            for row in range(size):
26                # Calculate the correct index for the value considering 1-based to 0-based indexing
27                value_index = matrix[row][col] - 1
28              
29                # If we have already seen this number in the current column, the matrix is not valid
30                if seen_col[value_index]:
31                    return False
32              
33                # Mark the number as seen in the current column
34                seen_col[value_index] = True
35
36        # If we reach this point, the matrix has unique numbers in all rows and all columns
37        return True
38

Java Solution

1class Solution {
2    public boolean checkValid(int[][] matrix) {
3        // Retrieve the size of the matrix, which is a square matrix (n x n)
4        int size = matrix.length;
5
6        // Check each row in the matrix
7        for (int row = 0; row < size; ++row) {
8            // Create a tracker for seen numbers in the current row
9            boolean[] seenRow = new boolean[size];
10            for (int col = 0; col < size; ++col) {
11                // Retrieve the number and convert it to an index (0 to n-1)
12                int numberIndex = matrix[row][col] - 1;
13                // Check if the number has already been seen in the current row
14                if (seenRow[numberIndex]) {
15                    // If the number is seen before, the matrix is not valid
16                    return false;
17                }
18                // Mark the number as seen
19                seenRow[numberIndex] = true;
20            }
21        }
22
23        // Check each column in the matrix
24        for (int col = 0; col < size; ++col) {
25            // Create a tracker for seen numbers in the current column
26            boolean[] seenColumn = new boolean[size];
27            for (int row = 0; row < size; ++row) {
28                // Retrieve the number and convert it to an index (0 to n-1)
29                int numberIndex = matrix[row][col] - 1;
30                // Check if the number has already been seen in the current column
31                if (seenColumn[numberIndex]) {
32                    // If the number is seen before, the matrix is not valid
33                    return false;
34                }
35                // Mark the number as seen
36                seenColumn[numberIndex] = true;
37            }
38        }
39        // If all rows and columns contain all numbers exactly once, matrix is valid
40        return true;
41    }
42}
43

C++ Solution

1class Solution {
2public:
3    // Function to check if the given matrix is valid
4    bool checkValid(vector<vector<int>>& matrix) {
5        int size = matrix.size(); // Get the size of the matrix
6      
7        // Check each row for validity
8        for (int rowIndex = 0; rowIndex < size; ++rowIndex) {
9            vector<bool> seenInRow(size, false); // Initialize seenInRow to keep track of numbers in row
10            for (int columnIndex = 0; columnIndex < size; ++columnIndex) {
11                int value = matrix[rowIndex][columnIndex] - 1; // Zero-based index for checking
12                if (seenInRow[value]) return false; // If the number is already seen, matrix is invalid
13                seenInRow[value] = true; // Mark the number as seen for current row
14            }
15        }
16
17        // Check each column for validity
18        for (int columnIndex = 0; columnIndex < size; ++columnIndex) {
19            vector<bool> seenInColumn(size, false); // Initialize seenInColumn to keep track of numbers in column
20            for (int rowIndex = 0; rowIndex < size; ++rowIndex) {
21                int value = matrix[rowIndex][columnIndex] - 1; // Zero-based index for checking
22                if (seenInColumn[value]) return false; // If the number is already seen, matrix is invalid
23                seenInColumn[value] = true; // Mark the number as seen for current column
24            }
25        }
26
27        // If all rows and columns pass the checks, return true indicating the matrix is valid
28        return true;
29    }
30};
31

Typescript Solution

1/**
2 * Checks if a given square matrix is valid. A matrix is valid if every row and every column
3 * contains all numbers from 1 to n (where n is the number of rows/columns in the matrix) exactly once.
4 *
5 * @param {number[][]} matrix - The square matrix to check for validity.
6 * @returns {boolean} - Returns true if the matrix is valid, false otherwise.
7 */
8function checkValid(matrix: number[][]): boolean {
9    const size = matrix.length;
10
11    // Create arrays to track the presence of numbers in each row and column.
12    let rows = Array.from({ length: size }, () => new Array(size).fill(false));
13    let columns = Array.from({ length: size }, () => new Array(size).fill(false));
14
15    // Iterate over each cell in the matrix.
16    for (let i = 0; i < size; i++) {
17        for (let j = 0; j < size; j++) {
18            // Get the current value, subtracting 1 to convert it to a 0-based index.
19            let currentValue = matrix[i][j] - 1;
20
21            // Check if the current value has already been seen in the current row or column.
22            if (rows[i][currentValue] || columns[j][currentValue]) {
23                return false; // If the value has been seen, return false as the matrix is invalid.
24            }
25
26            // Mark the value as seen for the current row and column.
27            rows[i][currentValue] = true;
28            columns[j][currentValue] = true;
29        }
30    }
31
32    // If we've checked all cells and have not returned false, the matrix is valid.
33    return true;
34}
35

Time and Space Complexity

The time complexity of the code is O(n^2). This is because there are two nested loops, each iterating n times, where n is the size of the matrix's dimension (both width and height). The first loop iterates through each row while the second inner loop checks each column for validating the matrix, ensuring all numbers from 1 to n appear exactly once in each row and column.

The space complexity of the code is O(n). This is because additional space is used to create the seen array which has a size of n. This array is used to track whether a number has been seen before in the current row or column. The seen array is reset to False for each row and column, but since it is reused, the space complexity does not exceed O(n).


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫