Check if Every Row and Column Contains All Numbers solution and explanation
9 more videos on this problem
Check if Every Row and Column Contains All Numbers | Leetcode 2133 | Contest 275 | 2 Approaches 🔥🔥🔥Coding Decoded · 6:08 · 2K views
Check if Every Row & Column Contains All Number | LeetCode 2133 | LeetCode Weekly 275| JAVA | HINDIPepcoding · 25:48 · 1K views
Check if Every Row and Column Contains All Numbers || LeetCode 2133 || Weekly LeetCode 275 ||Bro Coders · 4:28 · 1K views
2133. Check if Every Row and Column Contains All Numbers (Leetcode Easy)Programming Live with Larry · 4:14 · 1K views
2133. Check If Every Row and Column Contains All NumbersviralSongs · 3:03 · 1K views
2133. Check if Every Row and Column Contains All Numbers | LEETCODE EASYcode Explainer · 3:16 · 754 views
5976 Check if Every Row and Column Contains All Numbers| Check if Every Row and Column Contains AllEasy Code · 2:11 · 697 views
Leetcode 2133 Check if Every Row and Column Contains All Numbers & Leetcode 2126 Destroying AsteroidAlgorithmicIQ · 19:37 · 588 views
Check if Every Row and Column Contains All Numbers | LeetCode 2133The TryIt Project · 6:12 · 280 views
LeetCode 2133 | Check if Every Row and Column Contains All Numbers | HashSet | JavaSleepy Cracker · 5:14 · 127 views
The problem
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].length1 <= n <= 1001 <= matrix[i][j] <= n
Approach overview
Problem Overview: You are given an n x n matrix where values should range from 1 to n. The task is to verify that every row and every column contains all numbers from 1..n exactly once. If any row or column is missing a value or contains duplicates, the matrix is invalid.
Approach 1: Use Sets for Validation (Time: O(n2), Space: O(n))
This method uses a set to ensure uniqueness in each row and column. Iterate through the matrix row by row. For each row, insert elements into a set and verify that the set size becomes n while ensuring every value lies in the range 1..n. Repeat the same validation for every column. If any insertion encounters duplicates or invalid numbers, the matrix fails immediately. Set lookups and insertions are constant time on average, making the overall traversal O(n²).
This approach is intuitive and easy to implement. It relies on hash-based uniqueness checks, a common pattern when working with hash tables. Since each row and column requires its own temporary set, space usage stays at O(n). Most developers reach for this solution first because it is concise and hard to get wrong.
Approach 2: Use Count Arrays for Validation (Time: O(n2), Space: O(n))
Instead of hash sets, use a frequency array of size n + 1 for rows and columns. While iterating through a row, increment the count for matrix[i][j]. If the value is outside 1..n or its count exceeds 1, the row is invalid. Reset the array and repeat the process for each column. This approach replaces hashing with direct index access, which can be slightly faster and more memory predictable.
This pattern appears frequently in array and matrix validation problems where values fall within a known range. Since the value range is bounded by n, a counting structure becomes a natural fit.
Recommended for interviews: Both solutions run in O(n²) time, which is optimal because every cell must be inspected at least once. The set-based approach is typically preferred in interviews due to readability and fewer edge cases. The count-array version demonstrates deeper understanding of frequency tracking and constant-time indexing. Showing both approaches communicates strong problem-solving depth.
Approach 1: Approach 1: Use Sets for Validation
This approach leverages the property of sets to store unique elements. The idea is to use a set to check each row and column. For each row and column, we transform the elements into a set and compare it with a reference set containing all numbers from 1 to n. If both sets are equal for every row and column, the matrix is valid.
def checkValid(matrix):
n = len(matrix)
expected = set(range(1, n+1))
for i in range(n):
row_set = set(matrix[i])
col_set = set(matrix[j][i] for j in range(n))
if row_set != expected or col_set != expected:
return False
return Trueimport java.util.HashSet;
import java.util.Set;
class Solution {
public boolean checkValid(int[][] matrix) {
int n = matrix.length;
Set<Integer> expected = new HashSet<>();
for (int i = 1; i <= n; i++) expected.add(i);
for (int i = 0; i < n; i++) {
Set<Integer> rowSet = new HashSet<>();
Set<Integer> colSet = new HashSet<>();
for (int j = 0; j < n; j++) {
rowSet.add(matrix[i][j]);
colSet.add(matrix[j][i]);
}
if (!rowSet.equals(expected) || !colSet.equals(expected)) return false;
}
return true;
}
}#include <vector>
#include <unordered_set>
bool checkValid(std::vector<std::vector<int>>& matrix) {
int n = matrix.size();
std::unordered_set<int> expected;
for (int i = 1; i <= n; ++i) expected.insert(i);
for (int i = 0; i < n; ++i) {
std::unordered_set<int> row_set, col_set;
for (int j = 0; j < n; ++j) {
row_set.insert(matrix[i][j]);
col_set.insert(matrix[j][i]);
}
if (row_set != expected || col_set != expected) return false;
}
return true;
}var checkValid = function(matrix) {
let n = matrix.length;
let expected = new Set();
for (let i = 1; i <= n; i++) expected.add(i);
for (let i = 0; i < n; i++) {
let rowSet = new Set(matrix[i]);
let colSet = new Set();
for (let j = 0; j < n; j++) {
colSet.add(matrix[j][i]);
}
if (rowSet.size !== n || colSet.size !== n) return false;
if (!Array.from(rowSet).every(x => expected.has(x)) || !Array.from(colSet).every(y => expected.has(y))) return false;
}
return true;
};#include <stdbool.h>
#include <string.h>
bool checkValid(int** matrix, int matrixSize, int* matrixColSize) {
int n = matrixSize;
int expected[n + 1];
for(int i = 1; i <= n; i++) expected[i] = 0;
for(int i = 0; i < n; i++) {
int row[n + 1];
int col[n + 1];
memset(row, 0, sizeof(row));
memset(col, 0, sizeof(col));
for(int j = 0; j < n; j++) {
row[matrix[i][j]]++;
col[matrix[j][i]]++;
}
for(int k = 1; k <= n; k++) {
if(row[k] != 1 || col[k] != 1) return false;
}
}
return true;
}using System;
using System.Collections.Generic;
public class Solution {
public bool CheckValid(int[][] matrix) {
int n = matrix.Length;
var expected = new HashSet<int>();
for (int i = 1; i <= n; i++) expected.Add(i);
for (int i = 0; i < n; i++) {
var rowSet = new HashSet<int>();
var colSet = new HashSet<int>();
for (int j = 0; j < n; j++) {
rowSet.Add(matrix[i][j]);
colSet.Add(matrix[j][i]);
}
if (!rowSet.SetEquals(expected) || !colSet.SetEquals(expected)) return false;
}
return true;
}
}The Python solution utilizes sets for each row and column comparison, checking against a set of expected values from 1 to n.
Time Complexity: O(n^2), iterating through each element.
Space Complexity: O(n), using sets to store row and column data.
Approach 2: Approach 2: Use Count Arrays for Validation
This approach uses counting arrays to verify the numbers 1 to n in each row and column. We maintain a count of occurrences for each number in an row-count and column-count array. Post-increment in the matrix traversal, we check if every number from 1 to n appears exactly once.
def checkValid(matrix):
n = len(matrix)
rowCount = [[0] * n for _ in range(n)]
colCount = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
rowCount[i][matrix[i][j] - 1] += 1
colCount[j][matrix[i][j] - 1] += 1
for i in range(n):
for j in range(n):
if rowCount[i][j] != 1 or colCount[i][j] != 1:
return False
return Trueclass Solution {
public boolean checkValid(int[][] matrix) {
int n = matrix.length;
int[][] rowCount = new int[n][n];
int[][] colCount = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
rowCount[i][matrix[i][j] - 1]++;
colCount[j][matrix[i][j] - 1]++;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (rowCount[i][j] != 1 || colCount[j][j] != 1) return false;
}
}
return true;
}
}#include <vector>
bool checkValid(std::vector<std::vector<int>>& matrix) {
int n = matrix.size();
std::vector<std::vector<int>> rowCount(n, std::vector<int>(n));
std::vector<std::vector<int>> colCount(n, std::vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
rowCount[i][matrix[i][j] - 1]++;
colCount[j][matrix[i][j] - 1]++;
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (rowCount[i][j] != 1 || colCount[i][j] != 1) return false;
}
}
return true;
}var checkValid = function(matrix) {
let n = matrix.length;
let rowCount = Array.from({length: n}, () => Array(n).fill(0));
let colCount = Array.from({length: n}, () => Array(n).fill(0));
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
rowCount[i][matrix[i][j] - 1]++;
colCount[j][matrix[i][j] - 1]++;
}
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (rowCount[i][j] !== 1 || colCount[i][j] !== 1) return false;
}
}
return true;
};#include <stdbool.h>
#include <string.h>
bool checkValid(int** matrix, int matrixSize, int* matrixColSize) {
int n = matrixSize;
int rowCount[n][n];
int colCount[n][n];
memset(rowCount, 0, sizeof(rowCount));
memset(colCount, 0, sizeof(colCount));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
rowCount[i][matrix[i][j] - 1]++;
colCount[j][matrix[i][j] - 1]++;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (rowCount[i][j] != 1 || colCount[i][j] != 1) return false;
}
}
return true;
}public class Solution {
public bool CheckValid(int[][] matrix) {
int n = matrix.Length;
int[,] rowCount = new int[n,n];
int[,] colCount = new int[n,n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
rowCount[i,matrix[i][j] - 1]++;
colCount[j,matrix[i][j] - 1]++;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (rowCount[i,j] != 1 || colCount[i,j] != 1) return false;
}
}
return true;
}
}The Python solution uses nested lists to track occurrences of each number, ensuring that every number from 1 to n appears once in a matrix row and column.
Time Complexity: O(n^2), by iterating through matrix.
Space Complexity: O(n^2), using nested lists for counting integers.
Approach 3: Hash Table
Traverse each row and column of the matrix, using a hash table to record whether each number has appeared. If any number appears more than once in a row or column, return false; otherwise, return true
The time complexity is O(n^2), and the space complexity is O(n). Here, n is the size of the matrix.
function checkValid(matrix: number[][]): boolean {
const n = matrix.length;
const vis: boolean[] = Array(n + 1).fill(false);
for (const row of matrix) {
vis.fill(false);
for (const x of row) {
if (vis[x]) {
return false;
}
vis[x] = true;
}
}
for (let j = 0; j < n; ++j) {
vis.fill(false);
for (let i = 0; i < n; ++i) {
if (vis[matrix[i][j]]) {
return false;
}
vis[matrix[i][j]] = true;
}
}
return true;
}func checkValid(matrix [][]int) bool {
n := len(matrix)
for _, row := range matrix {
vis := make([]bool, n+1)
for _, x := range row {
if vis[x] {
return false
}
vis[x] = true
}
}
for j := 0; j < n; j++ {
vis := make([]bool, n+1)
for i := 0; i < n; i++ {
if vis[matrix[i][j]] {
return false
}
vis[matrix[i][j]] = true
}
}
return true
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Use Sets for Validation | Time Complexity: O(n^2), iterating through each element. |
| Approach 2: Use Count Arrays for Validation | Time Complexity: O(n^2), by iterating through matrix. |
| Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Use Sets for Validation | O(n²) | O(n) | Best general solution. Simple to implement with hash-based duplicate detection. |
| Use Count Arrays for Validation | O(n²) | O(n) | When values are guaranteed within 1..n and you want faster constant-time indexing without hashing. |
Frequently asked questions
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.
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.