Please see github.com/anusha-murali for all of my repositories.
This is a nice problem from LeetCode (Problem #2352)
Problem: Given a 0-indexed $n \times n$ integer matrix grid, return the number of pairs $(r_i, c_j)$ such that row $r_i$ and column $c_j$ 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).
Example 1:
\[\begin{bmatrix} 3 & 2 & 1 \\ 1 & 7 & 6 \\ 2 & 7 & 7 \end{bmatrix}\]Input: grid = [[3,2,1],[1,7,6],[2,7,7]]; Output: 1
Explanation: There is 1 equal row and column pair:
Example 2:
\[\begin{bmatrix} 3 & 1 & 2 & 2 \\ 1 & 4 & 4 & 5\\ 2 & 4 & 2 & 2\\ 2 & 4 & 2 & 2 \end{bmatrix}\]Input: grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]; Output: 3
Explanation: There are 3 equal row and column pairs:
Solution 1: We can compare each row of the matrix with each row of its transposed matrix.
For example, we can transpose the matrix in Example 2 and obtain the following transposed matrix, and then compare each row of the original matrix with each row of its transposed matrix.
\[\begin{bmatrix} 3 & 1 & 2 & 2 \\ 1 & 4 & 4 & 5\\ 2 & 4 & 2 & 2\\ 2 & 4 & 2 & 2 \end{bmatrix} \longrightarrow \begin{bmatrix} 3 & 1 & 2 & 2 \\ 1 & 4 & 4 & 4 \\ 2 & 4 & 2 & 2 \\ 2 & 5 & 2 & 2 \end{bmatrix}\]We can easily transpose a matrix, represented as list of lists, by using the zip()
function. The zip()
function takes iterables and aggregates them in a tuple. For example, list(zip([1, 2], [3, 4], [5, 6]))
will return [[1, 3, 5], [2, 4, 6]]
, where we first iterate through the corresponding elements in each of
the three lists and then generate a list. Therefore, using the zip()
function, we can construct the following solution to our problem:
def equalPairs(grid):
transpose = list(map(list, zip(*grid)))
count = 0
for i in range(len(grid)):
if grid[i] in transpose:
count += transpose.count(grid[i])
return count
Note that the zip()
function is being passed a packed argument. The packed argument syntax using *
implies that given a sequence of arguments args
, zip(*args)
will call zip()
such that each element in args
is a separate positional argument of zip()
. Since our argument grid
is a list of lists (matrix), the zip()
function will be called on each of the rows of the grid
.
Runtime: Ignoring the cost of transposing the matrix, the for
loop gives us a runtime of $O(n)$.
Solution 2: The Counter
is a subclass of dict
that can be used for counting hashable objects. The Counter
is a dictionary that hashes the objects as keys and their counts as values. We pass an iterable of hashable objects as an argument to the Counter
class’s constructor. For example, Counter(list("California"))
returns Counter({'a': 2, 'i': 2, 'C': 1, 'l': 1, 'f': 1, 'o': 1, 'r': 1, 'n': 1})
.
We can find the counts of each row occurring in grid
using, Counter(map(tuple, grid))
.
Similarly, we can find the counts of each row occurring in the transpose of grid
using, Counter(zip(*grid))
.
Therefore, our solution simplifies into the following:
def equalPairs(grid):
from collections import Counter
transpose_counts = Counter(zip(*grid))
grid_counts = Counter(map(tuple,grid))
return sum(transpose_counts[item]*grid_counts[item] for item in transpose_counts)
We iterate through each item in transpose_counts
and multiply the count corresponding to the item
with the count of the same item
in grid_counts
. The desired answer is the sum of these products.
For example, let us consider the grid in Example 2 above:
\[\begin{bmatrix} 3 & 1 & 2 & 2 \\ 1 & 4 & 4 & 5\\ 2 & 4 & 2 & 2\\ 2 & 4 & 2 & 2 \end{bmatrix}\]Our input is grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]
. Hence,
transpose_counts = Counter(zip(*grid)) = {(2, 4, 2, 2): 2, (3, 1, 2, 2): 1, (1, 4, 4, 5): 1}
grid_counts = Counter(map(tuple,grid)) = {(3, 1, 2, 2): 1, (1, 4, 4, 4): 1, (2, 4, 2, 2): 1, (2, 5, 2, 2): 1}
The tuple (2, 4, 2, 2)
has a count of 2 in the transposed matrix and a count of 1 in the original matrix. The tuple (3, 1, 2, 2)
has a count of 1 in both the transposed matrix and the original matrix. Therefore, our answer is, $2 \times 1 + 1 \times 1 = 3$.
Runtime: Since the for
loop iterates through the number of rows in the transposed matrix, the runtime is $O(n)$.