Check if Every Row and Column Contains All Numbers

To check if a given matrix is valid, we need to ensure that every row and every column contains all the integers from 1 to n (inclusive).

One approach to solve this problem is to iterate through each row and column of the matrix, and check if they contain all integers from 1 to n.

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def checkValid(self, matrix: List[List[int]]) -> bool:
        # Get the size of the matrix
        n = len(matrix)

        # Create a set of all numbers from 1 to n
        all_numbers = set(range(1, n + 1))

        # Check rows
        for row in matrix:
            if set(row) != all_numbers:
                return False

        # Check columns
        for j in range(n):
            column = [matrix[i][j] for i in range(n)]
            if set(column) != all_numbers:
                return False

        # If all rows and columns are valid, return True
        return True

In this solution, we first create a set of all numbers from 1 to n. Then we iterate over each row of the matrix and create a set from the elements in that row. If this set is not equal to the set of all numbers from 1 to n, we return False, indicating the matrix is not valid. We then do the same for each column of the matrix. If none of the rows or columns invalidate the matrix, we return True.

This solution has a time complexity of O(n^2) as we are iterating over each element of the matrix twice, once for the rows and once for the columns.