Rank Transform of a Matrix

Rank Transform of a Matrix

What is this problem about?

The Rank Transform of a Matrix problem asks you to assign a rank to each cell: the smallest element gets rank 1, tied elements in the same row or column must get the same rank, and ranks must be strictly greater than ranks of smaller elements in the same row or column. This hard coding problem uses Union-Find with sorted element processing. The array, matrix, union find, graph, sorting, and topological sort interview pattern is comprehensively tested.

Why is this asked in interviews?

Citadel, Meta, and Google ask this hard problem because it requires combining sorting with Union-Find to handle ties across rows and columns. Elements must be grouped by value, then within each group, cells sharing a row or column must receive the same rank (taking the maximum constraint from their group).

Algorithmic pattern used

Sort by value + Union-Find per value group. Sort all cells by value. Process groups of equal-value cells: union cells sharing a row or column within the same group. For each component, the rank = max(current_rank_in_row_or_col) + 1 across all cells in the component. Update row and column rank arrays.

Example explanation

Matrix=[[1,2],[3,4]]. All distinct: (0,0)→1, (0,1)→2, (1,0)→3, (1,1)→4.

• 1 at (0,0): no constraints. rank=1. row[0]=1, col[0]=1.
• 2 at (0,1): row[0]=1 → rank=max(1)+1=2. row[0]=2, col[1]=2.
• 3 at (1,0): col[0]=1 → rank=2. row[1]=2, col[0]=2.
• 4 at (1,1): row[1]=2, col[1]=2 → rank=3. Result: [[1,2],[2,3]].

Common mistakes candidates make

• Not grouping ties together before assigning ranks.
• Incorrect Union-Find: must union cells with same value in same row/column.
• Not taking max rank constraint across the entire component.
• Processing cells one-by-one instead of by value groups.

Interview preparation tip

Rank Transform of a Matrix combines Union-Find with value-based grouping. The algorithm has three phases: (1) sort all cells by value, (2) process each value group with Union-Find, (3) assign ranks based on component constraints. Practice this three-phase pattern on similar "ranked assignment with group constraints" problems.