Problem statement

An n x n matrix is valid when every row and every column contains each of the integers 1 to n (so each exactly once).

Given an n x n matrix whose entries are all between 1 and n, return true if it is valid.

Example 1

Input: matrix = [[3,1,2],[1,2,3],[2,3,1]]
Output: true

Example 2

Input: matrix = [[1,2,3],[2,3,1],[1,3,2]]
Output: false
Explanation: Every row is fine, but column 0 is [1,2,1]: it repeats 1 and misses 3.

Example 3

Input: matrix = [[1]]
Output: true

Constraints

• n == matrix.length == matrix[i].length
• 1 <= n <= 100
• 1 <= matrix[i][j] <= n

Hints for Check if Every Row and Column Contains All Numbers

1. Hint 1

   A line of n values drawn from 1..n contains every number exactly when it has no repeated value.

2. Hint 2

   So the task reduces to: no row and no column has a duplicate.

3. Hint 3

   Check row i and column i together with two 'seen' arrays of size n + 1.

How to solve Check if Every Row and Column Contains All Numbers

Since every entry is already in 1..n, a row or column of n entries covers all of 1..n if and only if it has no duplicates — so duplicate detection per line is enough.

Approach

1. For each i from 0 to n - 1, clear two boolean arrays row and col of size n + 1.
2. For each j, look at a = matrix[i][j] and b = matrix[j][i]; if row[a] or col[b] is already set, return false; otherwise set both.
3. Return true when every row and column passes.

Why it works

By the pigeonhole principle, n values from a set of size n with no repetition must use every value once. Checking row i and column i in the same loop visits each line exactly once.

Complexity

• Time — O(n^2)
• Space — O(n)

Pitfalls

• Checking only rows (or only sums) is not enough: [[1,2],[1,2]] has perfect rows but bad columns.
• Equal row sums prove nothing — [2,2,2] sums like [1,2,3].
• Reset the seen arrays for each new row and column.

Reference solution

Python

from typing import List

def checkValid(matrix: List[List[int]]) -> bool:
    n = len(matrix)
    for i in range(n):
        if len(set(matrix[i])) != n:
            return False
        if len(set(matrix[j][i] for j in range(n))) != n:
            return False
    return True

Java

public static boolean checkValid(int[][] matrix) {
    int n = matrix.length;
    for (int i = 0; i < n; i++) {
        boolean[] row = new boolean[n + 1], col = new boolean[n + 1];
        for (int j = 0; j < n; j++) {
            int a = matrix[i][j], b = matrix[j][i];
            if (row[a] || col[b]) return false;
            row[a] = true;
            col[b] = true;
        }
    }
    return true;
}

C++

bool checkValid(vector<vector<int>>& matrix) {
    int n = matrix.size();
    for (int i = 0; i < n; i++) {
        vector<bool> row(n + 1, false), col(n + 1, false);
        for (int j = 0; j < n; j++) {
            int a = matrix[i][j], b = matrix[j][i];
            if (row[a] || col[b]) return false;
            row[a] = true;
            col[b] = true;
        }
    }
    return true;
}

JavaScript

var checkValid = function(matrix) {
    var n = matrix.length;
    for (var i = 0; i < n; i++) {
        var row = new Array(n + 1).fill(false), col = new Array(n + 1).fill(false);
        for (var j = 0; j < n; j++) {
            var a = matrix[i][j], b = matrix[j][i];
            if (row[a] || col[b]) return false;
            row[a] = true;
            col[b] = true;
        }
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy