Check if Every Row and Column Contains All Numbers Python/Java solution

In Python, the solution usually creates a set for each row and column and checks if it contains n unique values. In Java, developers often use HashSet or an integer frequency array of size n+1. Both implementations iterate through the matrix and validate rows and columns in O(n^2) time.

How to solve Check if Every Row and Column Contains All Numbers in O(n)?

Solving the full problem in O(n) is not possible because the matrix contains n^2 elements that must be inspected. The optimal achievable complexity is O(n^2). Efficient solutions use either hash sets or frequency arrays to verify uniqueness while scanning rows and columns.

What is the best approach for Check if Every Row and Column Contains All Numbers?

The most common approach uses hash sets to validate each row and column. For every row and column, insert elements into a set and ensure the set size becomes n while values stay within the range 1..n. This runs in O(n^2) time and O(n) extra space, which is optimal because every matrix cell must be checked.

Is Check if Every Row and Column Contains All Numbers asked at Google/Amazon/Meta?

Matrix validation problems similar to this one appear frequently in interviews at companies like Amazon and Google. While the exact problem may vary, interviewers often test the ability to verify constraints in grids using hash sets, counting arrays, or matrix traversal techniques.

What data structure is used in Check if Every Row and Column Contains All Numbers?

The typical data structures are hash sets or counting arrays. Hash sets detect duplicates quickly during row or column traversal, while count arrays track frequency of values from 1..n using direct indexing. Both approaches maintain O(1) average lookup or update operations.

What is the time complexity of Check if Every Row and Column Contains All Numbers?

The time complexity is O(n^2). The algorithm must scan every cell of the n x n matrix at least once while validating rows and columns. Both the set-based and count-array approaches maintain this complexity, with constant-time insert or lookup operations during validation.

Description Hints 2 Solution Video 6:08

2133. Check if Every Row and Column Contains All Numbers

Q: Is Check if Every Row and Column Contains All Numbers easy or hard?

LeetCode classifies this problem as Easy. The challenge focuses on clean matrix traversal and duplicate detection. Developers comfortable with sets, arrays, and basic grid iteration can usually implement the optimal O(n^2) solution quickly.

Easy54.0% acceptance4 companies

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.

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

Asked at 4 companies

Karat Instacart Indeed Zoho

Topics

Hints open one at a time

Hint 1

Use for loops to check each row for every number from 1 to n. Similarly, do the same for each column.

Hint 2

For each check, you can keep a set of the unique elements in the checked row/col. By the end of the check, the size of the set should be n.

6:08

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution