Check if Every Row and Column Contains All Numbers

Difficulty: Easy | Acceptance: 54.10% | Paid: No Topics: Array, Hash Table, Matrix

You are given an n x n integer matrix matrix. Return true if the matrix is a Latin Square. Otherwise, return false.

A Latin Square is a matrix where:

Each row contains each number from 1 to n exactly once. Each column contains each number from 1 to n exactly once.

• Examples
• Constraints
• Hash Set
• Boolean Array
• Sorting

Examples

Example 1

Input:

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

Output:

true

Explanation: In this case, n = 3, and every row and column contains the numbers 1, 2, and 3. Hence, we return true.

Example 2

Input:

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

Output:

false

Explanation: In this case, n = 3, but the first row and the first column do not contain the numbers 2 or 3. Hence, we return false.

Constraints

n == matrix.length == matrix[i].length
1 <= n <= 100
1 <= matrix[i][j] <= n²

Hash Set

Intuition We can iterate through each row and each column, using a Hash Set to keep track of numbers we have already seen. If we encounter a duplicate or a number outside the range [1, n], the matrix is invalid.

Steps

• Iterate through each row index i from 0 to n-1.
• Create two empty sets, one for the current row and one for the current column.
• Iterate through each column index j from 0 to n-1.
• Check the value at matrix[i][j] (row) and matrix[j][i] (column).
• If the value is out of bounds (less than 1 or greater than n) or already exists in the corresponding set, return false.
• Otherwise, add the value to the set.
• If the loop completes without returning false, return true.

from typing import List

class Solution:
    def checkValid(self, matrix: List[List[int]]) -> bool:
        n = len(matrix)
        for i in range(n):
            row_set = set()
            col_set = set()
            for j in range(n):
                r_val = matrix[i][j]
                c_val = matrix[j][i]
                if r_val < 1 or r_val > n or r_val in row_set:
                    return False
                row_set.add(r_val)
                if c_val < 1 or c_val > n or c_val in col_set:
                    return False
                col_set.add(c_val)
        return True

Complexity

• Time: O(n²)
• Space: O(n)
• Notes: We use O(n) space for the sets. This is a standard approach for checking duplicates in a range.

Boolean Array

Intuition Since the numbers in the matrix are constrained to be between 1 and n², but we specifically only care about the presence of numbers 1 to n, we can use a boolean array of size n+1 to mark seen numbers. This is generally faster than a Hash Set due to lower overhead.

Steps

• Iterate through each row index i from 0 to n-1.
• Create two boolean arrays of size n+1, initialized to false, for the row and column.
• Iterate through each column index j from 0 to n-1.
• Check the value at matrix[i][j] and matrix[j][i].
• If the value is out of bounds or the corresponding index in the boolean array is already true, return false.
• Mark the index as true in the boolean array.
• If the loop completes, return true.

from typing import List

class Solution:
    def checkValid(self, matrix: List[List[int]]) -> bool:
        n = len(matrix)
        for i in range(n):
            row_seen = [False] * (n + 1)
            col_seen = [False] * (n + 1)
            for j in range(n):
                r_val = matrix[i][j]
                c_val = matrix[j][i]
                if r_val < 1 or r_val > n or row_seen[r_val]:
                    return False
                row_seen[r_val] = True
                if c_val < 1 or c_val > n or col_seen[c_val]:
                    return False
                col_seen[c_val] = True
        return True

Complexity

• Time: O(n²)
• Space: O(n)
• Notes: This approach is often faster in practice than using a Hash Set because it avoids hashing overhead.

Sorting

Intuition If a row or column contains all numbers from 1 to n exactly once, sorting it will result in the sequence [1, 2, …, n]. We can check this by sorting copies of the rows and columns.

Steps

• Iterate through each row index i from 0 to n-1.
• Create a copy of the current row and sort it.
• Create a list/array for the current column by iterating through rows, then sort it.
• Compare the sorted row and sorted column with the expected sequence [1, 2, …, n].
• If any mismatch occurs, return false.
• If all checks pass, return true.

from typing import List

class Solution:
    def checkValid(self, matrix: List[List[int]]) -> bool:
        n = len(matrix)
        for i in range(n):
            row = sorted(matrix[i])
            col = sorted(matrix[j][i] for j in range(n))
            if row != list(range(1, n + 1)) or col != list(range(1, n + 1)):
                return False
        return True

Complexity

• Time: O(n² log n)
• Space: O(n)
• Notes: Sorting takes O(n log n) for each of the n rows and n columns, resulting in a higher time complexity than the Hash Set or Boolean Array approaches.