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.

#2352

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

相等行列对

给你一个下标从 0 开始、大小为 n x n 的整数矩阵 grid ，返回满足 R i 行和 C j 列相等的行列对 (R i , C j ) 的数目。如果行和列以相同的顺序包含相同的元素（即相等的数组），则认为二者是相等的。示例 1：输入： grid = [[3,2,1],[1,7,6],…

数组哈希表矩阵模拟

题目描述

给你一个下标从 0 开始、大小为 n x n 的整数矩阵 grid ，返回满足 R_i 行和 C_j 列相等的行列对 (R_i, C_j) 的数目。

如果行和列以相同的顺序包含相同的元素（即相等的数组），则认为二者是相等的。

示例 1：

输入：grid = [[3,2,1],[1,7,6],[2,7,7]]
输出：1
解释：存在一对相等行列对：
- (第 2 行，第 1 列)：[2,7,7]

示例 2：

输入：grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]
输出：3
解释：存在三对相等行列对：
- (第 0 行，第 0 列)：[3,1,2,2]
- (第 2 行, 第 2 列)：[2,4,2,2]
- (第 3 行, 第 2 列)：[2,4,2,2]

提示：

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

lightbulb

解题思路

方法一：模拟

我们直接将矩阵 $grid$ 的每一行和每一列进行比较，如果相等，那么就是一对相等行列对，答案加一。

时间复杂度 $O(n^3)$ ，其中 $n$ 为矩阵 $grid$ 的行数或列数。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

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

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#3242 设计相邻元素求和服务 #2357 使数组中所有元素都等于零 #2365 任务调度器 II