2133. Check if Every Row and Column Contains All Numbers

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.

Solution Implementation

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).

Learn more about how to find time and space complexity quickly using problem constraints.