1
# Runtime: 3042 ms (Top 71.65%) | Memory: 50.4 MB (Top 92.27%)
2
class Solution:
3
    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:
4
        m, n = len(matrix), len(matrix[0])
5
        rank = [0] * (m + n)
6
        d = defaultdict(list)
7
        for i in range(m):
8
            for j in range(n):
9
                d[matrix[i][j]].append((i, j))
10

11
        def find(i):
12
            if p[i] != i:
13
                p[i] = find(p[i])
14
            return p[i]
15

16
        def union(i, j):
17
            pi, pj = find(i), find(j)
18
            p[pi] = pj
19
            newrank[pj] = max(newrank[pi], newrank[pj])
20

21
        for e in sorted(d):
22
            p = list(range(m + n))
23
            newrank = rank[:]
24
            for i, j in d[e]:
25
                union(i, m + j)
26
            for i, j in d[e]:
27
                rank[i] = rank[m + j] = matrix[i][j] = newrank[find(i)] + 1
28
        return matrix