#2352

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Equal Row and Column Pairs

Identify all pairs of rows and columns in a square matrix that contain identical elements in the same sequence efficiently.

array hash table matrix simulation

Problem Statement

You are given a 0-indexed n x n integer matrix grid. Your task is to determine the number of pairs (ri, cj) where row ri is exactly equal to column cj. Equality means both contain the same integers in the same order.

For example, in a matrix grid, check every row against every column and count each exact match. Return the total number of such equal row-column pairs.

Examples

Example 1

Input: grid = [[3,2,1],[1,7,6],[2,7,7]]

Output: 1

There is 1 equal row and column pair:

(Row 2, Column 1): [2,7,7]

Example 2

Input: grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]

Output: 3

There are 3 equal row and column pairs:

(Row 0, Column 0): [3,1,2,2]
(Row 2, Column 2): [2,4,2,2]
(Row 3, Column 2): [2,4,2,2]

Constraints

n == grid.length == grid[i].length
1 <= n <= 200
1 <= grid[i][j] <= 105

Solution Approach

Hash row representations

Convert each row into a tuple or string representation and store it in a hash map with its frequency. This allows O(1) lookup for matching columns.

Scan columns and match

Iterate through each column, build its representation, and check the hash map to count how many rows match this column exactly. Accumulate the total count.

Optimize for large matrices

Instead of comparing element by element repeatedly, use precomputed hash values for rows and columns to reduce the complexity from O(n^3) to O(n^2) on average.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) for creating row and column representations and O(n^2) for matching columns via hash lookup. Space complexity is O(n^2) for storing row representations in a hash map.

What Interviewers Usually Probe

You may ask if using a hash map is allowed for faster comparisons.
Expect hints about nested loops being inefficient for larger matrices.
Clarify whether matrix size can reach the upper bound of 200.

Common Pitfalls or Variants

Common pitfalls

Comparing arrays element by element without hashing leads to TLE on large n.
Not handling multiple identical rows or columns correctly when counting pairs.
Forgetting that order of elements matters; [1,2,3] is not equal to [3,2,1].

Follow-up variants

Count pairs where row and column sums are equal instead of exact sequences.
Allow approximate equality with a maximum difference threshold between elements.
Work with rectangular matrices where rows and columns may differ in length.

FAQ

What does 'Equal Row and Column Pairs' mean in this problem?

It means finding all pairs where a specific row and a specific column contain the same elements in exactly the same order.

Can we use a hash table for this comparison?

Yes, storing row representations in a hash map allows quick lookup when checking columns for equality.

What is the best way to handle multiple identical rows or columns?

Count the frequency of each unique row in a hash map and multiply by the matching column occurrences to get total pairs.

Will comparing element by element work for large matrices?

Direct element comparison is correct but inefficient for large n; using hashes or tuples avoids timeouts.

Does the order of elements in the row and column matter?

Yes, sequences must match exactly; any difference in order or value means the pair is not equal.

terminal

Solution

Solution 1: Simulation

We directly compare each row and column of the matrix $grid$. If they are equal, then it is a pair of equal row-column pairs, and we increment the answer by one.

1

2

3

4

5

6

7

8

class Solution:
    def equalPairs(self, grid: List[List[int]]) -> int:
        n = len(grid)
        ans = 0
        for i in range(n):
            for j in range(n):
                ans += all(grid[i][k] == grid[k][j] for k in range(n))
        return ans

Continue Practicing

#3242 design neighbor sum service #2357 make array zero by subtracting equal amounts #2365 task scheduler ii