How hard is LeetCode 1632. Rank Transform of a Matrix?

LeetCode 1632. Rank Transform of a Matrix is rated Hard on LeetCode.

What is the time complexity of LeetCode 1632. Rank Transform of a Matrix?

The Python solution on this page runs in O(V+E).

What is the space complexity of LeetCode 1632. Rank Transform of a Matrix?

The Python solution on this page uses O(V) auxiliary space.

What topics does LeetCode 1632. Rank Transform of a Matrix cover?

LeetCode 1632. Rank Transform of a Matrix is tagged Union Find, Graph, Topological Sort, Array, Matrix and Sorting on LeetCode.

Rank Transform of a Matrix — LeetCode 1632 Python Solution

HardUnion FindGraphTopological SortArrayMatrixSorting

Problem: #1632
Pattern: Topological Sort
Reading time: 8 min
Source: leetcode.com

The problem

Given an m x n matrix, return a new matrix answer where answer[row][col] is the rank of matrix[row][col]. The rank is an integer that represents how large an element is compared to other elements.

Example

Input: matrix = [[1,2],[3,4]]
Output: [[1,2],[2,3]]
Explanation: The rank of matrix[0][0] is 1 because it is the smallest integer in its row and column.

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(V+E)
Space	O(V) auxiliary

Pattern: Topological Sort

Order a set of tasks so that every dependency comes before the thing that needs it. LeetCode 1632. Rank Transform of a Matrix is filed here because LeetCode tags it Topological Sort, which is the vocabulary this hub collects.

The topological sort guide has the Python template for the pattern and the 32 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1632. Rank Transform of a Matrix?: LeetCode 1632. Rank Transform of a Matrix is rated Hard on LeetCode.
What is the time complexity of LeetCode 1632. Rank Transform of a Matrix?: The Python solution on this page runs in O(V+E).
What is the space complexity of LeetCode 1632. Rank Transform of a Matrix?: The Python solution on this page uses O(V) auxiliary space.
What topics does LeetCode 1632. Rank Transform of a Matrix cover?: LeetCode 1632. Rank Transform of a Matrix is tagged Union Find, Graph, Topological Sort, Array, Matrix and Sorting on LeetCode.