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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Check if Every Row and Column Contains All Numbers

Difficulty: Easy

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 an n x n integer matrix matrix, return true if the matrix is valid. Otherwise, return false.

Key Insights

  • Each row must contain all numbers from 1 to n.
  • Each column must also contain all numbers from 1 to n.
  • The problem can be solved using hash sets to track the presence of the required numbers.
  • The constraints ensure that matrix elements are within the valid range.

Space and Time Complexity

Time Complexity: O(n^2) - We need to check each element of the matrix. Space Complexity: O(n) - We use hash sets to store numbers for each row and each column.

Solution

To solve this problem, we will use hash sets to track the numbers present in each row and each column. We will iterate through each element of the matrix and add it to the corresponding row and column sets. After processing the entire matrix, we will check if each row and each column set contains exactly the numbers from 1 to n. If all sets are valid, we return true; otherwise, we return false.

Code Solutions

def checkValid(matrix):
    n = len(matrix)
    
    for i in range(n):
        row_set = set()
        col_set = set()
        
        for j in range(n):
            row_set.add(matrix[i][j])
            col_set.add(matrix[j][i])
        
        # Check if both the row and column contain all numbers from 1 to n
        if row_set != set(range(1, n + 1)) or col_set != set(range(1, n + 1)):
            return False
            
    return True
← Back to All Questions