Teaching Kids Programming – Check if Every Row and Column Contains All Numbers (XOR and Hash Set)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Use for loops to check each row for every number from 1 to n. Similarly, do the same for each column.
For each check, you can keep a set of the unique elements in the checked row/col. By the end of the check, the size of the set should be n.

Check if Every Row and Column Contains All Numbers using Set (Transpose Matrix)

First, we construct a target set that contains all numbers from 1 to N and then we can iterate each row and each column to check if they match the target set. To iterate the columns, we first can transpose the matrix e.g. using zip(*m) as a quick magic syntax sugar in Python.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def checkValid(self, matrix: List[List[int]]) -> bool:
        n = set(range(1, len(matrix) + 1))
        for r in matrix:
            if set(r) != n:
                return False
        for c in zip(*matrix):
            if set(c) != n:
                return False
        return True

class Solution:
    def checkValid(self, matrix: List[List[int]]) -> bool:
        n = set(range(1, len(matrix) + 1))
        for r in matrix:
            if set(r) != n:
                return False
        for c in zip(*matrix):
            if set(c) != n:
                return False
        return True

Time and space complexity is O(N^2) where N is the dimension of the square matrix (N rows and N columns)

Check if Every Row and Column Contains All Numbers by Checking the XOR value

Let x is the 1^2^3..N, then we use x to XOR each row and each column, the result should be zero otherwise it does not contain all numbers that row or column:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def checkValid(self, matrix: List[List[int]]) -> bool:       
        n = len(matrix)
        x = 0
        for i in range(1, n + 1):
            x ^= i            
        for r in range(n):
            rr = cc = x
            for c in range(n):
                rr ^= matrix[r][c]
                cc ^= matrix[c][r]
            if rr or cc:
                return False
        return True

class Solution:
    def checkValid(self, matrix: List[List[int]]) -> bool:       
        n = len(matrix)
        x = 0
        for i in range(1, n + 1):
            x ^= i            
        for r in range(n):
            rr = cc = x
            for c in range(n):
                rr ^= matrix[r][c]
                cc ^= matrix[c][r]
            if rr or cc:
                return False
        return True

A number XOR itself is zero. The time and space complexity is O(N^2) as we visit each number linear time.

–EOF (The Ultimate Computing & Technology Blog) —