Check if Every Row and Column Contains All Numbers

Check if Every Row and Column Contains All Numbers - 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.

Input & Output

Example 1 — Valid Matrix

$ Input: matrix = [[1,2,3],[2,3,1],[3,1,2]]

› Output: true

💡 Note: Each row contains [1,2,3] and each column contains [1,2,3] in some order. Row 1: [1,2,3]✓, Row 2: [2,3,1]✓, Row 3: [3,1,2]✓. Column 1: [1,2,3]✓, Column 2: [2,3,1]✓, Column 3: [3,1,2]✓

Example 2 — Invalid Matrix

$ Input: matrix = [[1,1,1],[1,2,3],[1,2,3]]

› Output: false

💡 Note: Row 1 contains [1,1,1] which is missing 2 and 3, and has duplicate 1s. This violates the requirement that each row must contain all numbers from 1 to n exactly once.

Example 3 — 2x2 Valid Matrix

$ Input: matrix = [[1,2],[2,1]]

› Output: true

💡 Note: For n=2, each row and column must contain [1,2]. Row 1: [1,2]✓, Row 2: [2,1]✓, Column 1: [1,2]✓, Column 2: [2,1]✓

Constraints

n == matrix.length == matrix[i].length
1 ≤ n ≤ 100
1 ≤ matrix[i][j] ≤ n

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

3x3 matrix where each cell contains numbers 1-3

Validate Rows

Check each row contains exactly {1,2,3}

Validate Columns

Check each column contains exactly {1,2,3}

Result

Return true if all pass, false otherwise

Key Takeaway

🎯 Key Insight: Each row and column must be a perfect permutation of numbers 1 to n

Asked in

a Amazon 15 G Google 12 M Microsoft 8 🍎 Apple 6

The key insight is that each row and column must be a perfect permutation of numbers 1 to n. Best approach uses boolean arrays for O(1) lookups to verify presence of all required numbers. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Hash Set Validation	O(n²)	O(n)	Use hash sets to check if each row/column contains exactly numbers 1 to n
Brute Force with Sorting	O(n³ log n)	O(n)	Sort each row and column, then check if they match [1,2,...,n]
Single Pass with Boolean Arrays	O(n²)	O(n²)	Use boolean arrays to track seen numbers in one pass through the matrix

Hash Set Validation — Algorithm Steps

For each row: add numbers to hash set, check set equals {1,2,...,n}
For each column: add numbers to hash set, check set equals {1,2,...,n}
Return true only if all pass validation

Visualization

Tap to expand

Step-by-Step Walkthrough

Row Check

Add row numbers to set, verify set = {1,2,3}

Column Check

Add column numbers to set, verify set = {1,2,3}

Result

Return true if all sets match expected

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int** matrix, int n) {
    // Check all rows
    for (int i = 0; i < n; i++) {
        bool seen[n + 1];
        memset(seen, false, sizeof(seen));
        
        for (int j = 0; j < n; j++) {
            int num = matrix[i][j];
            if (num < 1 || num > n || seen[num]) {
                return false;
            }
            seen[num] = true;
        }
        
        // Check all numbers 1 to n are present
        for (int k = 1; k <= n; k++) {
            if (!seen[k]) {
                return false;
            }
        }
    }
    
    // Check all columns
    for (int col = 0; col < n; col++) {
        bool seen[n + 1];
        memset(seen, false, sizeof(seen));
        
        for (int row = 0; row < n; row++) {
            int num = matrix[row][col];
            if (num < 1 || num > n || seen[num]) {
                return false;
            }
            seen[num] = true;
        }
        
        // Check all numbers 1 to n are present
        for (int k = 1; k <= n; k++) {
            if (!seen[k]) {
                return false;
            }
        }
    }
    
    return true;
}

int main() {
    // Simple parsing for small test cases
    int n = 3;
    int** matrix = malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        matrix[i] = malloc(n * sizeof(int));
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }
    
    bool result = solution(matrix, n);
    printf(result ? "true\n" : "false\n");
    
    for (int i = 0; i < n; i++) {
        free(matrix[i]);
    }
    free(matrix);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Visit each cell once for row check + once for column check = 2n² = O(n²)

⚠ Quadratic Growth

Space Complexity

O(n)

Hash set stores up to n numbers for validation

⚡ Linearithmic Space

25.4K Views

Medium Frequency

~12 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Set Validation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler