Solution Explanation: Check if Every Row and Column Contains All Numbers

This problem asks us to determine if an n x n matrix is valid, meaning every row and every column contains all integers from 1 to n (inclusive). We can solve this efficiently using a hash table (or set in Python) approach.

Approach:

The core idea is to check each row and each column independently to see if they contain all numbers from 1 to n without duplicates. We can achieve this using a hash table (or set) to track the occurrence of each number.

1. Row Check: Iterate through each row of the matrix. For each row:

   • Initialize an empty hash table (or set).
   • Iterate through the elements of the row.
   • For each element, check if it's already in the hash table. If it is, the row is invalid (duplicate found), and we return false.
   • If not, add the element to the hash table.
   • After processing all elements of the row, check if the size of the hash table equals n. If not, the row is invalid (missing numbers), and we return false.

2. Column Check: Similarly, iterate through each column of the matrix. For each column:

   • Initialize an empty hash table (or set).
   • Iterate through the elements of the column (accessing them using matrix[i][j] where j is fixed for the column).
   • Perform the same checks as in the row check: Check for duplicates and ensure all numbers from 1 to n are present.

3. Return true: If both the row and column checks pass without returning false, it means the matrix is valid, so we return true.

Time Complexity: We iterate through each element of the matrix twice (once for rows, once for columns). Therefore, the time complexity is O(n²), where n is the size of the matrix.

Space Complexity: The space complexity is O(n) because, in the worst case, we use a hash table (or set) of size n to store the numbers in a row or column.

Code Implementation (Python):

from itertools import chain
 
class Solution:
    def checkValid(self, matrix: List[List[int]]) -> bool:
        n = len(matrix)
        return all(len(set(row)) == n for row in chain(matrix, zip(*matrix)))

This Python solution elegantly uses itertools.chain to combine rows and columns and set to efficiently check for duplicates and the presence of all numbers 1 to n. zip(*matrix) transposes the matrix, effectively providing the columns as iterables.

Code Implementation (Java, C++, Go, TypeScript):

The Java, C++, Go, and TypeScript solutions follow a similar structure to the Python solution described in the Approach section. They explicitly iterate through rows and columns, using boolean arrays (vis) to track seen numbers.

Example (Java):

class Solution {
    public boolean checkValid(int[][] matrix) {
        int n = matrix.length;
        boolean[] vis = new boolean[n + 1]; //boolean array for efficient duplicate check
 
        //Row Check
        for (int[] row : matrix) {
            Arrays.fill(vis, false); //Reset for each row
            for (int x : row) {
                if (vis[x]) return false; //Duplicate found
                vis[x] = true;
            }
            for(int i=1; i<=n; ++i){
                if(!vis[i]) return false; //Missing number
            }
        }
 
        //Column Check
        for (int j = 0; j < n; ++j) {
            Arrays.fill(vis, false); //Reset for each column
            for (int i = 0; i < n; ++i) {
                int x = matrix[i][j];
                if (vis[x]) return false; //Duplicate found
                vis[x] = true;
            }
            for(int i=1; i<=n; ++i){
                if(!vis[i]) return false; //Missing number
            }
        }
        return true;
    }
}

The other language implementations are structurally similar, using their respective data structures for efficient duplicate detection. The key is the two-pass approach (rows, then columns) and the use of a hash table or boolean array for efficient lookup.