Problem Description

You are given an n x n integer matrix and need to determine if it's valid according to a specific rule.

A matrix is considered valid if:

• Every row contains all integers from 1 to n (inclusive)
• Every column contains all integers from 1 to n (inclusive)

In other words, each row must have exactly the numbers 1, 2, 3, ..., n with no duplicates or missing values, and the same requirement applies to each column.

For example, if n = 3, then each row should contain exactly the numbers 1, 2, 3 in some order, and each column should also contain exactly the numbers 1, 2, 3 in some order.

The task is to check whether the given matrix satisfies these conditions and return true if it's valid, or false otherwise.

The solution uses a clever approach with Python's set data structure and the zip(*matrix) operation to transpose the matrix. By checking that each row has exactly n unique elements (using len(set(row)) == n), we ensure all numbers from 1 to n are present without duplicates. The chain function combines the original rows with the transposed columns, allowing us to check both rows and columns in a single operation.

Intuition

The key insight is recognizing that if a row or column contains all integers from 1 to n, it must have exactly n distinct values. Since we're working with exactly n positions and need exactly the numbers 1 through n, there's no room for duplicates or missing values.

Think about it this way: if we have n slots and need to place n specific numbers (1 to n), the only way this works is if each number appears exactly once. If any number appears twice, another number must be missing. If any number is outside the range [1, n], then some required number is missing.

This leads us to a simple validation strategy: convert each row and column to a set and check if its size equals n. A set automatically removes duplicates, so if len(set(row)) == n, we know:

• There are no duplicates (otherwise the set would be smaller)
• All numbers must be in the range [1, n] (otherwise we couldn't have exactly n distinct values in an n-length row)

The elegant part of the solution is using zip(*matrix) to transpose the matrix, which turns columns into rows. This allows us to treat columns the same way we treat rows. By using chain(matrix, zip(*matrix)), we create a single iterable containing all rows followed by all columns, enabling us to check everything in one pass with the all() function.

This approach avoids explicitly checking if each number from 1 to n exists, relying instead on the mathematical property that n distinct values in n positions with the constraint that values must be from 1 to n guarantees a valid configuration.

Solution Approach

The solution uses a hash table (implemented as Python's set) to track unique elements in each row and column. Here's how the implementation works:

Step 1: Get the matrix dimension

• Extract n = len(matrix) to know the expected size and range of values

Step 2: Transform columns into rows

• Use zip(*matrix) to transpose the matrix
• This operation takes the i-th element from each row and groups them into a new tuple, effectively turning columns into rows
• For example, if matrix is [[1,2],[3,4]], then zip(*matrix) produces [(1,3), (2,4)]

Step 3: Combine rows and columns

• Use chain(matrix, zip(*matrix)) to create a single iterable containing all original rows followed by all transposed columns
• This allows us to process both rows and columns with the same logic

Step 4: Validate each row and column

• For each row (or transposed column) in the chained iterable:
  • Convert it to a set to get unique elements
  • Check if len(set(row)) == n
  • If the set has exactly n elements, it means all numbers from 1 to n are present without duplicates

Step 5: Return the result

• Use the all() function to ensure every row and column passes the validation
• If any row or column has len(set(row)) != n, the all() function returns False
• Only if all rows and columns have exactly n unique elements does it return True

The hash table approach is efficient because:

• Creating a set from a row/column takes O(n) time
• We check 2n sequences (n rows + n columns)
• Total time complexity: O(n²)
• Space complexity: O(n) for the temporary sets created

Example Walkthrough

Let's walk through a small example with a 3×3 matrix to illustrate the solution approach.

Example Matrix:

matrix = [[1, 2, 3],
          [3, 1, 2],
          [2, 3, 1]]

Step 1: Get matrix dimension

• n = len(matrix) = 3
• We expect each row and column to contain exactly the numbers 1, 2, and 3

Step 2: Transform columns into rows using zip(*matrix)

• zip(*matrix) transposes the matrix:
  • Column 0: (1, 3, 2) - takes first element from each row
  • Column 1: (2, 1, 3) - takes second element from each row
  • Column 2: (3, 2, 1) - takes third element from each row

Step 3: Combine rows and columns with chain

• chain(matrix, zip(*matrix)) creates:

  [
    [1, 2, 3],  # Row 0
    [3, 1, 2],  # Row 1
    [2, 3, 1],  # Row 2
    (1, 3, 2),  # Column 0 (transposed)
    (2, 1, 3),  # Column 1 (transposed)
    (3, 2, 1)   # Column 2 (transposed)
  ]

Step 4: Validate each sequence

• Row 0: set([1, 2, 3]) = {1, 2, 3}, length = 3 ✓
• Row 1: set([3, 1, 2]) = {1, 2, 3}, length = 3 ✓
• Row 2: set([2, 3, 1]) = {1, 2, 3}, length = 3 ✓
• Column 0: set((1, 3, 2)) = {1, 2, 3}, length = 3 ✓
• Column 1: set((2, 1, 3)) = {1, 2, 3}, length = 3 ✓
• Column 2: set((3, 2, 1)) = {1, 2, 3}, length = 3 ✓

Step 5: Return result

• Since all 6 checks pass (len(set(row)) == 3 for each), all() returns True
• The matrix is valid!

Counter-example to show failure:

matrix = [[1, 2, 3],
          [2, 2, 1],  # Invalid: has duplicate 2, missing 3
          [3, 1, 2]]

• Row 1: set([2, 2, 1]) = {1, 2}, length = 2 ≠ 3 ✗
• The all() function would return False immediately upon checking this row

Solution Implementation

Time and Space Complexity

Time Complexity: O(n^2)

The code iterates through all elements in the matrix twice:

• First iteration: checking each row in matrix (n rows × n elements per row = n^2 operations)
• Second iteration: checking each column via zip(*matrix) which transposes the matrix (n columns × n elements per column = n^2 operations)

For each row/column, set(row) creates a set which takes O(n) time, and this is done 2n times total. Additionally, len(set(row)) comparison is O(1). Therefore, the total time complexity is O(n) × 2n = O(n^2).

Space Complexity: O(n)

The space complexity comes from:

• Creating a set for each row/column check, which can contain at most n elements: O(n)
• The zip(*matrix) operation creates a transposed view of the matrix, but since it's evaluated lazily in the generator expression and only one column is processed at a time, it uses O(n) space for the current column being checked
• The chain iterator itself uses O(1) space

The maximum space used at any point is O(n) for the set creation during validation of each row or column.

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

Common Pitfalls

Pitfall 1: Not Validating the Actual Values

The current solution only checks if each row and column has n unique elements, but doesn't verify that these elements are specifically the integers from 1 to n.

For example, if n = 3 and a row contains [0, 2, 4], the solution would incorrectly return True because there are 3 unique elements, even though the valid values should be [1, 2, 3].

Example of incorrect validation:

matrix = [[0, 2], 
          [3, 4]]  # n=2, but contains 0,3,4 instead of 1,2
# Current solution returns True (incorrectly)
# Should return False

Solution: Add explicit value range checking:

def checkValid(self, matrix: List[List[int]]) -> bool:
    n = len(matrix)
    valid_set = set(range(1, n + 1))  # {1, 2, ..., n}
  
    # Check if each row contains exactly the values 1 to n
    for row in matrix:
        if set(row) != valid_set:
            return False
  
    # Check if each column contains exactly the values 1 to n
    for col in zip(*matrix):
        if set(col) != valid_set:
            return False
  
    return True

Pitfall 2: Assuming Matrix is Square

The solution assumes the input matrix is always square (n x n), but doesn't handle edge cases where the matrix might be rectangular or empty.

Example of edge case:

matrix = [[1, 2, 3],
          [3, 1, 2]]  # 2x3 matrix, not square
# Could cause unexpected behavior

Solution: Add validation for matrix dimensions:

def checkValid(self, matrix: List[List[int]]) -> bool:
    if not matrix or not matrix[0]:
        return False
  
    n = len(matrix)
    # Verify matrix is square
    if any(len(row) != n for row in matrix):
        return False
  
    valid_set = set(range(1, n + 1))
    return all(set(row) == valid_set for row in chain(matrix, zip(*matrix)))

Pitfall 3: Performance with Large Matrices

While the current solution is already O(n²), creating sets repeatedly for each row and column can be memory-intensive for very large matrices, especially when using chain() which might create additional overhead.

Solution for better memory usage: Process rows and columns separately to avoid holding too many temporary objects:

def checkValid(self, matrix: List[List[int]]) -> bool:
    n = len(matrix)
    valid_set = set(range(1, n + 1))
  
    # Check rows first
    if not all(set(row) == valid_set for row in matrix):
        return False
  
    # Then check columns
    return all(set(col) == valid_set for col in zip(*matrix))

This approach allows earlier termination if rows are invalid, potentially saving computation on columns.