LeetCode 2133 - Check if Every Row and Column Contains All Numbers

In this problem, we are given an n x n matrix where every value is guaranteed to be between 1 and n. A matrix is considered valid if every row contains all integers from 1 through n exactly once, and every column also contains all integers from 1 through n exactly once.

leetcodeeasyarrayhash-tablematrix

LeetCode Problem 2133

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Matrix

Solution

Problem Understanding

In this problem, we are given an n x n matrix where every value is guaranteed to be between 1 and n. A matrix is considered valid if every row contains all integers from 1 through n exactly once, and every column also contains all integers from 1 through n exactly once.

Another way to think about it is that each row and column must form a complete permutation of the numbers 1 to n. If any number is missing, duplicated, or replaced incorrectly in a row or column, the matrix is invalid.

The input is a square matrix:

  • matrix[i][j] represents the value at row i and column j
  • n is the number of rows and columns

The expected output is:

  • true if every row and every column contains all integers from 1 to n
  • false otherwise

The constraints are relatively small:

  • 1 <= n <= 100
  • Every element is already guaranteed to be in the valid range 1 to n

These constraints tell us several important things:

  • We do not need to worry about invalid numeric ranges
  • An O(n^2) or even O(n^3) solution is acceptable because n is at most 100
  • Simplicity and correctness are more important than heavy optimization

An important observation is that duplicates automatically imply a missing value, because every row and column must contain exactly n numbers from a set of size n.

Some edge cases that can cause mistakes include:

  • A row with duplicate numbers
  • A column with duplicate numbers
  • A matrix of size 1 x 1
  • Rows that are valid individually, but columns are not
  • Columns that fail late in the traversal

The problem guarantees that all values are between 1 and n, so we only need to verify uniqueness and completeness.

Approaches

Brute Force Approach

The brute force approach checks every row and every column independently against the expected set {1, 2, ..., n}.

For each row:

  1. Create a frequency count or set
  2. Insert all row values
  3. Verify that every number from 1 to n exists exactly once

Then repeat the same process for every column.

This approach is correct because a matrix is valid if and only if all rows and columns contain the full required set of numbers.

A very naive brute force implementation might repeatedly scan rows and columns to verify every number individually. For example, for each row and each number from 1 to n, we could search the entire row to see if the number exists. That creates unnecessary repeated work.

Although this still works within constraints, it is less efficient and less elegant.

Optimal Approach

The better approach uses hash sets to validate rows and columns in a single traversal.

For each row:

  • Create a set
  • Insert all row values
  • If the set size is not n, duplicates exist

For each column:

  • Create another set
  • Insert all column values
  • If the set size is not n, duplicates exist

Because values are guaranteed to lie within 1 to n, a set of size n automatically means every required number appears exactly once.

The key insight is that uniqueness plus valid range implies completeness.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(1) Repeatedly scans rows and columns for every expected number
Optimal O(n²) O(n) Uses hash sets to validate rows and columns efficiently

Algorithm Walkthrough

  1. Determine the matrix size n.

Since the matrix is square, the number of rows is also the number of columns. 2. Iterate through every row index i.

For each row, create an empty set called row_values. This set tracks which numbers appear in the current row. 3. Iterate through every column index j within the row.

Insert matrix[i][j] into row_values. 4. After processing the row, check the set size.

If the size is not equal to n, then some number is duplicated and another number is missing. Return False. 5. Repeat the same process for columns.

For each column index j, create a new set called column_values. 6. Traverse all rows for the current column.

Insert matrix[i][j] into column_values. 7. Validate the column set size.

If the size is not equal to n, the column is invalid. Return False. 8. If all rows and columns pass validation, return True.

Why it works

Every value in the matrix is guaranteed to be between 1 and n. Therefore, if a row or column contains exactly n unique values, it must contain all numbers from 1 to n.

The algorithm checks this property for every row and every column. If any row or column violates the condition, the matrix is invalid. Otherwise, the matrix satisfies the definition of validity.

Python Solution

from typing import List

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

        # Check every row
        for row in matrix:
            if len(set(row)) != n:
                return False

        # Check every column
        for col in range(n):
            column_values = set()

            for row in range(n):
                column_values.add(matrix[row][col])

            if len(column_values) != n:
                return False

        return True

The implementation begins by storing the matrix size in n.

The first loop validates every row. Converting a row into a set removes duplicates automatically. If the resulting set size is smaller than n, then some value appeared more than once.

The second section validates columns. Since columns are not directly stored as lists, we build a temporary set manually by traversing all rows for a fixed column index.

If any row or column fails validation, the function immediately returns False. This early exit avoids unnecessary work.

If the algorithm finishes all checks successfully, the matrix satisfies the required conditions and the function returns True.

Go Solution

func checkValid(matrix [][]int) bool {
	n := len(matrix)

	// Check rows
	for i := 0; i < n; i++ {
		rowSet := make(map[int]bool)

		for j := 0; j < n; j++ {
			rowSet[matrix[i][j]] = true
		}

		if len(rowSet) != n {
			return false
		}
	}

	// Check columns
	for j := 0; j < n; j++ {
		colSet := make(map[int]bool)

		for i := 0; i < n; i++ {
			colSet[matrix[i][j]] = true
		}

		if len(colSet) != n {
			return false
		}
	}

	return true
}

The Go implementation follows the same logic as the Python version, but uses map[int]bool to simulate a hash set.

Go does not have a built in set type, so inserting keys into a map and checking the map length is the standard approach.

Since all integers are small and within constraints, there are no concerns about integer overflow.

Slices are used naturally for matrix traversal, and no special handling for empty or nil matrices is required because the problem guarantees valid input dimensions.

Worked Examples

Example 1

Input:

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

Row Validation

Row Index Row Values Set Contents Set Size Valid?
0 [1,2,3] {1,2,3} 3 Yes
1 [3,1,2] {1,2,3} 3 Yes
2 [2,3,1] {1,2,3} 3 Yes

Column Validation

Column Index Column Values Set Contents Set Size Valid?
0 [1,3,2] {1,2,3} 3 Yes
1 [2,1,3] {1,2,3} 3 Yes
2 [3,2,1] {1,2,3} 3 Yes

All rows and columns are valid, so the algorithm returns True.

Example 2

Input:

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

Row Validation

Row Index Row Values Set Contents Set Size Valid?
0 [1,1,1] {1} 1 No

The first row already fails because duplicates exist and numbers 2 and 3 are missing.

The algorithm immediately returns False without checking further rows or columns.

Complexity Analysis

Measure Complexity Explanation
Time O(n²) Every matrix cell is visited a constant number of times
Space O(n) Each temporary set stores at most n values

The algorithm traverses all rows and columns once. Since the matrix contains n² elements, the total runtime is O(n²).

The extra space comes from the temporary hash set used for each row or column. At most, the set contains n elements.

Test Cases

sol = Solution()

# Provided example 1
assert sol.checkValid([
    [1, 2, 3],
    [3, 1, 2],
    [2, 3, 1]
]) == True  # fully valid matrix

# Provided example 2
assert sol.checkValid([
    [1, 1, 1],
    [1, 2, 3],
    [1, 2, 3]
]) == False  # duplicate values in row and column

# Minimum size matrix
assert sol.checkValid([
    [1]
]) == True  # single element matrix

# Invalid row
assert sol.checkValid([
    [1, 2],
    [1, 1]
]) == False  # second row missing value 2

# Invalid column
assert sol.checkValid([
    [1, 2],
    [2, 2]
]) == False  # second column duplicates 2

# Larger valid matrix
assert sol.checkValid([
    [1, 2, 3, 4],
    [2, 3, 4, 1],
    [3, 4, 1, 2],
    [4, 1, 2, 3]
]) == True  # Latin square structure

# Duplicate in last column
assert sol.checkValid([
    [1, 2, 3],
    [2, 3, 1],
    [3, 1, 1]
]) == False  # last column invalid

# Duplicate in first row only
assert sol.checkValid([
    [2, 2, 1],
    [1, 3, 2],
    [3, 1, 2]
]) == False  # first row invalid

Test Summary

Test Why
Valid 3x3 matrix Confirms correct behavior on standard valid input
Invalid duplicated row Ensures duplicate detection works
1x1 matrix Verifies smallest boundary case
Invalid row Tests row failure logic
Invalid column Tests column failure logic
Larger valid matrix Confirms scalability and correctness
Duplicate in last column Ensures late column failures are detected
Duplicate in first row Verifies early termination behavior

Edge Cases

A 1 x 1 matrix is the smallest possible input. Since the only allowed value is 1, the matrix is automatically valid if it contains that number. Some implementations accidentally overcomplicate this case, but the set based approach handles it naturally because the row and column sets both have size 1.

Another important edge case is when rows are valid individually but columns are not. For example:

[
  [1, 2],
  [1, 2]
]

Each row contains both required numbers, but the columns contain duplicates. An implementation that only validates rows would incorrectly return True. The algorithm avoids this bug by validating rows and columns separately.

A third important case occurs when duplicates appear late in traversal. For example, the first several rows and columns may be correct before a failure appears near the end of the matrix. The implementation correctly continues validation until every row and column has been checked, unless an earlier failure allows an immediate return.

Another subtle case is repeated values combined with the valid range guarantee. Because values are guaranteed to lie between 1 and n, checking only the set size is sufficient. If the constraints allowed arbitrary integers, we would also need to explicitly verify that every number belonged to the required range.