2133. Check if Every Row and Column Contains All Numbers

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

Solution

Version 1: o(n*n)

'matrix' must consist of values from 1 to 3 only

所以我们可以用SET去重在做

• Time: O(n^2)O(n2)

• Space: O(n)O(n)

 public boolean checkValid(int[][] matrix) {
        
        int n = matrix.length;
        
        for(int i = 0; i< n; i++)
        {
            Set<Integer> row = new HashSet<>();
            Set<Integer> col = new HashSet<>();
            for(int j = 0; j< n ; j++)
            {
                row.add(matrix[i][j]);
                col.add(matrix[j][i]);
            }
            if(Math.min(row.size(), col.size()) <n)
            {
                return false;
            }
        }
        return true;
        
    }

如果没有testcase限制， 'matrix' must consist of values from 1 to 3 only ，可以加上min, max控制：

class Solution {
    public boolean checkValid(int[][] matrix) {
        
        int n = matrix.length;
        
        for(int i = 0; i< n; i++)
        {
            Set<Integer> row = new HashSet<>();
            Set<Integer> col = new HashSet<>();
            int rowMin = Integer.MAX_VALUE;
            int rowMax = Integer.MIN_VALUE;
            int colMin = rowMin;
            int colMax = rowMax;
            for(int j = 0; j< n ; j++)
            {
                if(!row.contains(matrix[i][j]))
                {
                    row.add(matrix[i][j]);
                    rowMin = Math.min(rowMin, matrix[i][j]);
                    rowMax = Math.max(rowMax, matrix[i][j]);
                }else
                {
                    return false;
                }
                
                if(!col.contains(matrix[j][i]))
                {
                    col.add(matrix[j][i]);
                    colMin = Math.min(colMin, matrix[j][i]);
                    colMax = Math.max(colMax, matrix[j][i]);
                }else
                {
                    return false;
                }
            }
            
            if(rowMin != 1 || colMin != 1 || rowMax != n || colMax != n )
            {
                return false;
            }
        } 
        return true;
        
    }
}

Version 2: 空间换时间

https://poitevinpm.medium.com/leetcode-2133-check-if-every-row-and-column-contains-all-numbers-15e10127293f