algoadvance

You are given an n x n integer matrix matrix. The matrix contains all the integers from 1 to n. Your task is to check if every row and every column contains all the integers from 1 to n.

Return true if every row and every column of the matrix contains all the integers from 1 to n, otherwise return false.

Clarifying Questions

1. What is the range of the values of n?
   • n can vary, but let’s assume it fits within reasonable memory constraints, so 1 <= n <= 100.
2. Can we assume the given matrix is always square?
   • Yes, the matrix is always n x n.
3. Is there any specific data type we need to ensure in our return type?
   • The function should return a boolean.

Strategy

1. Validation of Individual Rows and Columns: To ensure each row and column contains all numbers from 1 to n, we can use sets for comparison since set operations (like union and difference) are efficient.

2. Steps:

   • Create a reference set containing all numbers from 1 to n.
   • For each row and each column in the matrix, create a set for the numbers in that row/column.
   • Compare the set of each row and column with the reference set.
   • If any row or column does not match the reference set, return false.
   • If all rows and columns match the reference set, return true.

Code

def checkValid(matrix):
    n = len(matrix)
    reference_set = set(range(1, n + 1))

    # Check all rows
    for row in matrix:
        if set(row) != reference_set:
            return False
    
    # Check all columns
    for col in range(n):
        column_set = set(matrix[row][col] for row in range(n))
        if column_set != reference_set:
            return False

    return True

Time Complexity

• Time Complexity: O(n^2)
  • We traverse every element in the n x n matrix twice (once for rows and once for columns).
  • Set operations (creation and comparison) are O(n) for each row and column, summing to O(n^2).
• Space Complexity: O(n)
  • We are using additional space for the reference set and the sets used for individual rows and columns, which takes up linear space relative to n.

Explanation

1. Reference Set Creation: We create a set called reference_set consisting of numbers from 1 to n.
2. Row Validation: For each row in the matrix, we convert it to a set and compare it to reference_set. If any row does not match, we return false.
3. Column Validation: Similarly, we construct sets for each column by iterating through each row and accumulating values for the column indices. Compare these column sets with reference_set. If any column does not match, return false.
4. If All Valid: If both row and column checks pass, return true.

This ensures that every row and column contains all the integers from 1 to n.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?