Check if Every Row and Column Contains All Numbers

Check if Every Row and Column Contains All Numbers

What is this problem about?

The "Check if Every Row and Column Contains All Numbers interview question" is a grid validation task similar to checking a Sudoku board. You are given an $n imes n$ matrix. You need to verify if every single row and every single column contains all the integers from 1 to $n$.

Why is this asked in interviews?

Companies like Instacart and Karat use the "Check if Every Row and Column Contains All Numbers coding problem" to assess basic matrix traversal and the use of "Hash Table interview pattern" structures for uniqueness checks. It tests whether a candidate can efficiently validate constraints in a 2D space without redundant passes.

Algorithmic pattern used

This problem follows the Set-based Uniqueness Check pattern.

1. Row Validation: For each row, add all elements to a hash set. Check if the set size is $n$ and if all elements are within the range $[1, n]$.
2. Column Validation: For each column, do the same.
3. Combined Pass: You can perform both checks in a single nested loop structure. For each $(r, c)$, use two sets or boolean arrays: rows[r] and cols[c].

Example explanation

Matrix $3 imes 3$:

1 2 3
3 1 2
2 3 1

• Row 0: {1, 2, 3}. Size 3. OK.
• Col 0: {1, 3, 2}. Size 3. OK. ... all other rows and columns follow. Result: True.

Common mistakes candidates make

• Range Check: Only checking if the set size is $n$, but forgetting to ensure the numbers are specifically $1..n$. (Wait, if size is $n$ and numbers are $1..n$, then every number must appear exactly once. If the numbers are outside the range, then size $n$ isn't enough).
• Redundant Passes: Traversing the whole matrix once for rows and then once again for columns. While $O(N^2)$, it's less clean than a single nested loop.
• Space Complexity: Creating $2N$ hash sets. While acceptable for $O(N^2)$ time, using a boolean frequency array can be faster and more memory-efficient.

Interview preparation tip

Whenever you need to check for "completeness" or "uniqueness" in a set of $N$ items from $1..N$, a boolean array of size $N$ or a bitmask is often more performant than a Hash Set. This is a common "Matrix interview pattern" optimization.