Teaching Kids Programming – Algorithms to Count Equal Row and Column Pairs in a Square Matrix using Hash Map

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a 0-indexed n x n integer matrix grid, return the number of pairs (Ri, Cj) such that row Ri and column Cj are equal. A row and column pair is considered equal if they contain the same elements in the same order (i.e. an equal array).

equal-rows-and-columns-pairs-matrix

Hints:
We can use nested loops to compare every row against every column.
Another loop is necessary to compare the row and column element by element.
It is also possible to hash the arrays and compare the hashed values instead.

Count Equal Row and Column Pairs using Hash Map

The bruteforce approach would be to iterate over rows and count how many columns are equal to rows or (vice versa). Iterating takes O(N^2) time and comparison takes another O(N) thus total time O(N^3).

We can certainly do better. We can make a tuple from a row or column and use it as the key to a hash map aka dictionary. Then we can count the rows and columns separately in two hash maps or Counters, then we can sum up the multiplication of the values with the same keys.

1
2
3
4
5
6
7
8
9

class Solution:
    def equalPairs(self, grid: List[List[int]]) -> int:   
        rows = defaultdict(int)
        cols = defaultdict(int)
        for r in grid:
            rows[tuple(r)] += 1
        for c in zip(*grid):
            cols[tuple(c)] += 1
        return sum(rows[k] * cols[k] for k in rows) # or for k in cols

class Solution:
    def equalPairs(self, grid: List[List[int]]) -> int:   
        rows = defaultdict(int)
        cols = defaultdict(int)
        for r in grid:
            rows[tuple(r)] += 1
        for c in zip(*grid):
            cols[tuple(c)] += 1
        return sum(rows[k] * cols[k] for k in rows) # or for k in cols

We can use the Counter to replace the defaultdict:

1
2
3
4
5

class Solution:
    def equalPairs(self, grid: List[List[int]]) -> int:   
        rows = Counter(tuple(r) for r in grid)
        cols = Counter(tuple(c) for c in zip(*grid))
        return sum(rows[k] * cols[k] for k in rows) # or for k in cols

class Solution:
    def equalPairs(self, grid: List[List[int]]) -> int:   
        rows = Counter(tuple(r) for r in grid)
        cols = Counter(tuple(c) for c in zip(*grid))
        return sum(rows[k] * cols[k] for k in rows) # or for k in cols

We can just use one Counter and then iterate over the columns and sum them separately.

1
2
3
4

class Solution:
    def equalPairs(self, grid: List[List[int]]) -> int:
        rows = Counter(tuple(r) for r in grid)
        return sum(rows[k] for k in zip(*grid))

class Solution:
    def equalPairs(self, grid: List[List[int]]) -> int:
        rows = Counter(tuple(r) for r in grid)
        return sum(rows[k] for k in zip(*grid))

The tuples are immutable so they are hashable. We use zip(*M) to obtain the iterator to the columns. *M removes the external dimension/brackets.

The time complexity is O(N^2) and the space complexity is O(N).

–EOF (The Ultimate Computing & Technology Blog) —