#1632

Hard

auto_awesomeGraph indegree plus topological ordering

LeetCode Problem Workspace

Rank Transform of a Matrix

Compute a unique rank matrix using graph indegree with topological ordering, ensuring each element reflects its relative size accurately.

array union find graph topological sort sorting

Problem Statement

Given an m x n matrix, return a new matrix answer where each answer[row][col] represents the rank of matrix[row][col]. The rank is the smallest integer that satisfies the ordering rules across both rows and columns.

The rank of an element is calculated such that it is strictly greater than any smaller elements in the same row or column. Equal elements in the same row or column may share ranks. The input guarantees that the resulting rank matrix is unique under these constraints.

Examples

Example 1

Input: matrix = [[1,2],[3,4]]

Output: [[1,2],[2,3]]

The rank of matrix[0][0] is 1 because it is the smallest integer in its row and column. The rank of matrix[0][1] is 2 because matrix[0][1] > matrix[0][0] and matrix[0][0] is rank 1. The rank of matrix[1][0] is 2 because matrix[1][0] > matrix[0][0] and matrix[0][0] is rank 1. The rank of matrix[1][1] is 3 because matrix[1][1] > matrix[0][1], matrix[1][1] > matrix[1][0], and both matrix[0][1] and matrix[1][0] are rank 2.

Example 2

Input: matrix = [[7,7],[7,7]]

Output: [[1,1],[1,1]]

Example details omitted.

Example 3

Input: matrix = [[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]]

Output: [[4,2,3],[1,3,4],[5,1,6],[1,3,4]]

Example details omitted.

Constraints

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

Solution Approach

Sort and Group Equal Elements

Flatten the matrix and sort cells by value. Use Union Find to link elements that are equal and must share the same rank, ensuring that dependencies in rows and columns are maintained.

Build Dependency Graph

For each row and column, create directed edges from smaller ranks to larger ones. This captures the required ordering constraints as a graph, ready for topological sorting to assign consistent ranks.

Assign Ranks via Topological Sort

Perform a topological sort on the graph, assigning ranks starting from 1 and incrementing along dependencies. Union Find ensures tied elements are assigned identical ranks while respecting row and column constraints.

Complexity Analysis

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

Time 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).

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1

#### Python3

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

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

Continue Practicing

#1697 checking existence of edge length limited paths #1728 cat and mouse ii #2328 number of increasing paths in a grid