What pattern does Rank Transform of a Matrix rely on?

It relies on graph indegree plus topological ordering to assign ranks uniquely while respecting row and column dependencies.

Can equal elements in the same row or column have different ranks?

No, equal elements must share the same rank and be merged using Union Find before rank assignment.

What is the main time complexity factor in this problem?

Sorting the cells by value dominates the time complexity, followed by graph construction and topological sorting.

How do I handle large matrices efficiently?

Use Union Find for grouping equal elements and sparse adjacency lists for graph edges to reduce overhead.

Why is topological sorting necessary for assigning ranks?

Topological sorting ensures that every element’s rank is larger than all smaller elements in the same row or column, maintaining uniqueness.

#1632

Hard

auto_awesome并查集

LeetCode 题解工作台

矩阵转换后的排名

给你一个 m x n 的矩阵 matrix ，请你返回一个新的矩阵 answer ，其中 answer[row][col] 是 matrix[row][col] 的排名。每个元素的排名是一个整数，表示这个元素相对于其他元素的大小关系，它按照如下规则计算：排名是从 1 开始的一个整数。如果两…

数组并查集图拓扑排序排序

题目描述

给你一个 m x n 的矩阵 matrix ，请你返回一个新的矩阵 answer ，其中 answer[row][col] 是 matrix[row][col] 的排名。

每个元素的排名是一个整数，表示这个元素相对于其他元素的大小关系，它按照如下规则计算：

排名是从 1 开始的一个整数。
如果两个元素 p 和 q 在 同一行 或者 同一列 ，那么：
- 如果 p < q ，那么 rank(p) < rank(q)
- 如果 p == q ，那么 rank(p) == rank(q)
- 如果 p > q ，那么 rank(p) > rank(q)
排名需要越小越好。

题目保证按照上面规则 answer 数组是唯一的。

示例 1：

输入：matrix = [[1,2],[3,4]]
输出：[[1,2],[2,3]]
解释：
matrix[0][0] 的排名为 1 ，因为它是所在行和列的最小整数。
matrix[0][1] 的排名为 2 ，因为 matrix[0][1] > matrix[0][0] 且 matrix[0][0] 的排名为 1 。
matrix[1][0] 的排名为 2 ，因为 matrix[1][0] > matrix[0][0] 且 matrix[0][0] 的排名为 1 。
matrix[1][1] 的排名为 3 ，因为 matrix[1][1] > matrix[0][1]， matrix[1][1] > matrix[1][0] 且 matrix[0][1] 和 matrix[1][0] 的排名都为 2 。

示例 2：

输入：matrix = [[7,7],[7,7]]
输出：[[1,1],[1,1]]

示例 3：

输入：matrix = [[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]]
输出：[[4,2,3],[1,3,4],[5,1,6],[1,3,4]]

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 500
-10⁹ <= matrix[row][col] <= 10⁹

lightbulb

解题思路

方法一：排序 + 并查集

我们先考虑简化情形：没有相同的元素。那么显然最小的元素的秩为 $1$ ，第二小的元素则要考虑是否和最小元素同行或同列。于是得到贪心解法：从小到大遍历元素，并维护每行、每列的最大秩，该元素的秩即为同行、同列的最大秩加 $1$ 。见题目：2371. 最小化网格中的最大值。

存在相同元素时则较为复杂，假设两个相同元素同行（或同列），那么就要考虑到两个元素分别对应的行（或列）的最大秩。同时还可能出现联动，比如元素 a 和 b 同行，b 和 c 同列，那么要同时考虑这三个元素。

这种联动容易想到并查集，于是我们用并查集将元素分为几个连通块，对于每个连通块，里面所有元素对应的行或列的最大秩加 $1$ ，即为该连通块内所有元素的秩。

时间复杂度 $O(m \times n \times \log(m \times n))$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别为矩阵的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, a, b):
        pa, pb = self.find(a), self.find(b)
        if pa != pb:
            if self.size[pa] > self.size[pb]:
                self.p[pb] = pa
                self.size[pa] += self.size[pb]
            else:
                self.p[pa] = pb
                self.size[pb] += self.size[pa]

    def reset(self, x):
        self.p[x] = x
        self.size[x] = 1


class Solution:
    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:
        m, n = len(matrix), len(matrix[0])
        d = defaultdict(list)
        for i, row in enumerate(matrix):
            for j, v in enumerate(row):
                d[v].append((i, j))
        row_max = [0] * m
        col_max = [0] * n
        ans = [[0] * n for _ in range(m)]
        uf = UnionFind(m + n)
        for v in sorted(d):
            rank = defaultdict(int)
            for i, j in d[v]:
                uf.union(i, j + m)
            for i, j in d[v]:
                rank[uf.find(i)] = max(rank[uf.find(i)], row_max[i], col_max[j])
            for i, j in d[v]:
                ans[i][j] = row_max[i] = col_max[j] = 1 + rank[uf.find(i)]
            for i, j in d[v]:
                uf.reset(i)
                uf.reset(j + m)
        return ans

speed

复杂度分析

指标	值
时间	complexity is dominated by sorting cells O(m _n_ log(m _n)) and graph processing. Space complexity depends on storing parent arrays for Union Find and adjacency lists for topological sorting, typically O(m_ n).
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Watch for correctly linking equal elements to avoid rank conflicts.
question_mark
Check for proper graph edge creation between dependent elements in rows and columns.
question_mark
Ensure topological sort respects both row and column ordering constraints to maintain uniqueness.

warning

常见陷阱

外企场景

error
Failing to merge equal elements before building dependencies, causing incorrect rank assignments.
error
Ignoring column or row constraints when adding graph edges, leading to invalid topological ordering.
error
Assuming ranks can be assigned greedily without topological sorting, which breaks uniqueness in some matrices.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Apply the same approach to a 1D array to assign relative ranks respecting duplicates.
arrow_right_alt
Compute ranks only for a single row or column subset while maintaining graph indegree ordering.
arrow_right_alt
Use the algorithm for sparse matrices where most entries are zero, optimizing Union Find and graph storage.

help

常见问题

外企场景

继续练习

#1697 检查边长度限制的路径是否存在 #1728 猫和老鼠 II #2328 网格图中递增路径的数目