We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check if Every Row and Column Contains All Numbers

Number: 2254

Difficulty: Easy

Paid? No

Companies: Karat, Zoho, Indeed, Instacart

Problem Description

An n x n matrix is valid if every row and every column contains all the integers from 1 to n (inclusive). Given such a matrix, determine if it is valid. Return true if every row and every column contains all numbers from 1 to n; otherwise, return false.

Key Insights

  • Each row must contain all numbers from 1 to n with no duplicates.
  • Each column must also contain all numbers from 1 to n.
  • Use a set to compare the elements in each row and column with the expected set {1, 2, ..., n}.
  • Iterate through the matrix first by rows and then by columns to perform the necessary checks.

Space and Time Complexity

Time Complexity: O(n²) - Each element of the matrix is examined once. Space Complexity: O(n) - A set of size n is used for verification during row and column checks.

Solution

The solution involves:

  1. Creating an expected set containing numbers from 1 to n.
  2. Iterating through each row, converting it into a set, and comparing it with the expected set.
  3. Iterating through each column, collecting the elements into a set, and comparing it with the expected set. If any row or column fails the check, the function immediately returns false. If all checks pass, the function returns true. This approach efficiently verifies that both rows and columns meet the problem requirements.

Code Solutions

# Function to check if matrix is valid
def checkValid(matrix):
    # Determine the size of the matrix
    n = len(matrix)
    # Expected set of numbers from 1 to n
    expected = set(range(1, n + 1))
    
    # Verify each row
    for row in matrix:
        # If the set of the row does not match the expected, return False
        if set(row) != expected:
            return False
            
    # Verify each column
    for col in range(n):
        # Create set for the current column
        col_set = set(matrix[row][col] for row in range(n))
        # If the set does not match the expected, return False
        if col_set != expected:
            return False
            
    # All rows and columns are valid
    return True

# Example usage:
example_matrix = [[1,2,3], [3,1,2], [2,3,1]]
print(checkValid(example_matrix))  # Expected output: True
← Back to All Questions