LeetCode 1632 - Rank Transform of a Matrix

The problem asks us to assign a rank to every element in a matrix while preserving ordering relationships inside rows and columns. For any two elements that share the same row or the same column: - If one value is smaller, its rank must also be smaller.

leetcodehardarrayunion-findgraph-theorytopological-sortsortingmatrix

LeetCode Problem 1632

Difficulty: 🔴 Hard
Topics: Array, Union-Find, Graph Theory, Topological Sort, Sorting, Matrix

Solution

Problem Understanding

The problem asks us to assign a rank to every element in a matrix while preserving ordering relationships inside rows and columns.

For any two elements that share the same row or the same column:

  • If one value is smaller, its rank must also be smaller.
  • If two values are equal, their ranks must also be equal.

Additionally, the assigned ranks must be as small as possible while satisfying all constraints.

The input is an m x n matrix where:

  • m and n can each be as large as 500
  • Values may be negative
  • Values may repeat many times

The output is another matrix of the same dimensions where each position contains the computed rank.

The important challenge is that equal values connected through rows and columns must receive the same rank. This creates groups of cells that must be processed together. A naive local comparison approach fails because rank dependencies can propagate across the matrix.

For example:

1 2
3 4

The value 4 must have rank 3, not rank 2, because it is greater than both 2 and 3, and those already require rank 2.

The constraints are large enough that expensive repeated propagation or graph relaxation approaches will time out. A solution must efficiently process up to 250,000 cells.

Several edge cases are especially important:

  • Multiple equal values in the same row or column
  • Equal values connected indirectly through chains
  • Negative numbers
  • Single row or single column matrices
  • Large groups of repeated values
  • Cases where equal values must share a rank even though they appear far apart

The problem guarantees that a unique minimum valid ranking exists.

Approaches

Brute Force Approach

A brute force solution would repeatedly try to update ranks until all row and column constraints are satisfied.

One possible implementation would:

  1. Initialize all ranks to 1
  2. Compare every pair of cells sharing a row or column
  3. If ordering constraints are violated, increase ranks
  4. Repeat until no changes occur

This eventually converges because ranks only increase and the constraints are finite.

However, this approach is extremely inefficient. Each iteration may scan many row and column relationships, and many iterations may be required before ranks stabilize.

With up to 250,000 cells, repeated propagation becomes far too expensive.

Key Insight

The critical observation is that matrix values should be processed in sorted order.

Suppose we already know the final ranks for all smaller values. Then for a current value:

  • Its rank must be one greater than the maximum rank already present in its row or column.
  • Equal values connected through rows or columns must be merged together and assigned the same rank.

This naturally suggests:

  1. Sort cells by value
  2. Process equal values together
  3. Use Union-Find to group connected equal-value cells
  4. Track the maximum rank already assigned to each row and column

The Union-Find structure is essential because equal values may form connected components through rows and columns.

For example:

7 7
7 7

All four cells must share the same rank.

Even more subtle cases exist where equality connections are indirect.

By processing values in ascending order, we ensure all smaller dependencies are already resolved before assigning the next rank.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O((mn)^2) or worse O(mn) Repeatedly propagates rank constraints until stable
Optimal O(mn log(mn)) O(mn) Sorts values and uses Union-Find for equal groups

Algorithm Walkthrough

  1. Create a mapping from value to all positions containing that value.

We process values in ascending order because smaller values determine the minimum valid ranks for larger values. 2. Maintain an array called rank.

The first m positions represent row ranks.

The next n positions represent column ranks.

rank[i] stores the maximum rank already assigned in that row or column. 3. Process matrix values in sorted order.

For every distinct value:

  • Gather all cells containing that value.
  • Build connected components among equal-value cells using Union-Find.
  1. Build Union-Find groups.

For each cell (r, c):

  • Treat row r and column c as nodes.
  • Union row node r with column node c + m.

This connects all equal-value cells sharing rows or columns. 5. Group cells by their Union-Find root.

Cells in the same component must receive the same rank because they are equal and connected through row/column relationships. 6. Compute the rank for each component.

For every cell (r, c) in a component:

  • The new rank must exceed both:

  • the current rank of row r

  • the current rank of column c

Therefore:

new_rank = max(rank[r], rank[c + m]) + 1

The component rank is the maximum such value across all cells in the component. 7. Assign the computed rank to every cell in the component. 8. Update row and column rank trackers.

After assigning ranks:

  • rank[r] = component_rank
  • rank[c + m] = component_rank

This ensures larger future values build on correct dependencies.

Why it works

Processing values in ascending order guarantees that all smaller values already have finalized ranks. Union-Find ensures that all connected equal-value cells are treated as one unit. The algorithm always assigns the smallest possible rank consistent with existing row and column constraints. Because every assignment is minimal and dependencies are processed in sorted order, the final ranking is both valid and minimal.

Python Solution

from typing import List
from collections import defaultdict

class UnionFind:
    def __init__(self):
        self.parent = {}

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

    def union(self, x, y):
        self.parent[self.find(x)] = self.find(y)

class Solution:
    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:
        rows = len(matrix)
        cols = len(matrix[0])

        value_positions = defaultdict(list)

        for r in range(rows):
            for c in range(cols):
                value_positions[matrix[r][c]].append((r, c))

        answer = [[0] * cols for _ in range(rows)]

        # rank[i] for rows, rank[rows + j] for columns
        rank = [0] * (rows + cols)

        for value in sorted(value_positions):
            uf = UnionFind()

            positions = value_positions[value]

            # Build connected components
            for r, c in positions:
                uf.union(r, c + rows)

            groups = defaultdict(list)

            # Group cells by connected component
            for r, c in positions:
                root = uf.find(r)
                groups[root].append((r, c))

            updates = []

            # Compute rank for each component
            for group in groups.values():
                max_rank = 0

                for r, c in group:
                    max_rank = max(
                        max_rank,
                        rank[r],
                        rank[c + rows]
                    )

                new_rank = max_rank + 1

                for r, c in group:
                    answer[r][c] = new_rank
                    updates.append((r, c, new_rank))

            # Apply updates after processing entire value
            for r, c, new_rank in updates:
                rank[r] = new_rank
                rank[c + rows] = new_rank

        return answer

The implementation begins by grouping matrix positions according to their values. This allows all equal values to be processed together.

The rank array tracks the highest assigned rank for every row and column. Rows occupy indices [0, rows-1], while columns occupy [rows, rows+cols-1].

For each distinct value, a fresh Union-Find structure is created. Rows and columns connected by equal-value cells are unioned together. This creates components representing cells that must share the same rank.

After building components, the algorithm computes the smallest valid rank for each group by examining the maximum existing row and column ranks.

The updates are stored temporarily because all equal-value cells must be processed simultaneously. Updating ranks immediately could incorrectly affect other cells with the same value.

Finally, the computed ranks are written into the answer matrix and row/column trackers are updated.

Go Solution

package main

import (
	"sort"
)

type UnionFind struct {
	parent map[int]int
}

func NewUnionFind() *UnionFind {
	return &UnionFind{
		parent: make(map[int]int),
	}
}

func (uf *UnionFind) Find(x int) int {
	if _, exists := uf.parent[x]; !exists {
		uf.parent[x] = x
	}

	if uf.parent[x] != x {
		uf.parent[x] = uf.Find(uf.parent[x])
	}

	return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) {
	rootX := uf.Find(x)
	rootY := uf.Find(y)

	if rootX != rootY {
		uf.parent[rootX] = rootY
	}
}

func matrixRankTransform(matrix [][]int) [][]int {
	rows := len(matrix)
	cols := len(matrix[0])

	valuePositions := make(map[int][][]int)

	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			val := matrix[r][c]
			valuePositions[val] = append(valuePositions[val], []int{r, c})
		}
	}

	values := make([]int, 0, len(valuePositions))

	for val := range valuePositions {
		values = append(values, val)
	}

	sort.Ints(values)

	answer := make([][]int, rows)

	for i := range answer {
		answer[i] = make([]int, cols)
	}

	rank := make([]int, rows+cols)

	for _, val := range values {
		uf := NewUnionFind()

		positions := valuePositions[val]

		for _, pos := range positions {
			r := pos[0]
			c := pos[1]

			uf.Union(r, c+rows)
		}

		groups := make(map[int][][]int)

		for _, pos := range positions {
			r := pos[0]
			c := pos[1]

			root := uf.Find(r)
			groups[root] = append(groups[root], []int{r, c})
		}

		type Update struct {
			rank int
			row  int
			col  int
		}

		updates := []Update{}

		for _, group := range groups {
			maxRank := 0

			for _, pos := range group {
				r := pos[0]
				c := pos[1]

				if rank[r] > maxRank {
					maxRank = rank[r]
				}

				if rank[c+rows] > maxRank {
					maxRank = rank[c+rows]
				}
			}

			newRank := maxRank + 1

			for _, pos := range group {
				r := pos[0]
				c := pos[1]

				answer[r][c] = newRank

				updates = append(updates, Update{
					rank: newRank,
					row:  r,
					col:  c,
				})
			}
		}

		for _, upd := range updates {
			rank[upd.row] = upd.rank
			rank[upd.col+rows] = upd.rank
		}
	}

	return answer
}

The Go implementation follows the same logic as the Python solution. Because Go does not provide built-in dictionaries with default initialization, the Union-Find Find method explicitly initializes missing parents.

Slices are used instead of tuples for coordinate storage. Structs are used for update tracking because Go does not support lightweight tuple syntax.

No integer overflow concerns exist because ranks never exceed m + n.

Worked Examples

Example 1

Input:

[[1,2],
 [3,4]]

Step 1: Group by Value

Value Positions
1 (0,0)
2 (0,1)
3 (1,0)
4 (1,1)

Initial rank array:

[0,0,0,0]

Rows use indices 0,1

Columns use indices 2,3

Process Value 1

Cell (0,0) connects row 0 and column 2.

Current max:

max(rank[0], rank[2]) = max(0,0) = 0

Assign rank:

1

Updated:

answer =
[[1,0],
 [0,0]]

rank =
[1,0,1,0]

Process Value 2

Cell (0,1) connects row 0 and column 3.

Current max:

max(1,0) = 1

Assign:

2

Updated:

answer =
[[1,2],
 [0,0]]

rank =
[2,0,1,2]

Process Value 3

Cell (1,0) connects row 1 and column 2.

Current max:

max(0,1) = 1

Assign:

2

Updated:

answer =
[[1,2],
 [2,0]]

rank =
[2,2,2,2]

Process Value 4

Cell (1,1) connects row 1 and column 3.

Current max:

max(2,2) = 2

Assign:

3

Final answer:

[[1,2],
 [2,3]]

Example 2

Input:

[[7,7],
 [7,7]]

All cells belong to one connected component.

Every row and column initially has rank 0.

Therefore all cells receive:

1

Final answer:

[[1,1],
 [1,1]]

Example 3

Input:

[[20,-21,14],
 [-19,4,19],
 [22,-47,24],
 [-19,4,19]]

Sorted values:

-47, -21, -19, 4, 14, 19, 20, 22, 24

Processing proceeds in ascending order.

Important connected components:

Value Connected Cells
-19 (1,0), (3,0)
4 (1,1), (3,1)
19 (1,2), (3,2)

These equal values share rows and columns, so Union-Find merges them and assigns equal ranks.

Final result:

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

Complexity Analysis

Measure Complexity Explanation
Time O(mn log(mn)) Sorting distinct values dominates
Space O(mn) Hash maps, Union-Find, and answer matrix

The matrix contains mn cells. Grouping positions takes linear time. Sorting values costs O(mn log(mn)) in the worst case when all values are distinct.

Union-Find operations are nearly constant time because of path compression. Every cell participates in only a small number of operations.

The space usage is linear because we store position groups, Union-Find structures, rank trackers, and the output matrix.

Test Cases

from typing import List

class Solution:
    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:
        from collections import defaultdict

        class UnionFind:
            def __init__(self):
                self.parent = {}

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

            def union(self, x, y):
                self.parent[self.find(x)] = self.find(y)

        rows = len(matrix)
        cols = len(matrix[0])

        value_positions = defaultdict(list)

        for r in range(rows):
            for c in range(cols):
                value_positions[matrix[r][c]].append((r, c))

        answer = [[0] * cols for _ in range(rows)]
        rank = [0] * (rows + cols)

        for value in sorted(value_positions):
            uf = UnionFind()

            positions = value_positions[value]

            for r, c in positions:
                uf.union(r, c + rows)

            groups = defaultdict(list)

            for r, c in positions:
                groups[uf.find(r)].append((r, c))

            updates = []

            for group in groups.values():
                max_rank = 0

                for r, c in group:
                    max_rank = max(
                        max_rank,
                        rank[r],
                        rank[c + rows]
                    )

                new_rank = max_rank + 1

                for r, c in group:
                    answer[r][c] = new_rank
                    updates.append((r, c, new_rank))

            for r, c, new_rank in updates:
                rank[r] = new_rank
                rank[c + rows] = new_rank

        return answer

sol = Solution()

assert sol.matrixRankTransform([[1,2],[3,4]]) == [[1,2],[2,3]]  # basic increasing matrix

assert sol.matrixRankTransform([[7,7],[7,7]]) == [[1,1],[1,1]]  # all equal values

assert sol.matrixRankTransform(
    [[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]]
) == [[4,2,3],[1,3,4],[5,1,6],[1,3,4]]  # complex dependency example

assert sol.matrixRankTransform([[1]]) == [[1]]  # single cell matrix

assert sol.matrixRankTransform([[1,2,3]]) == [[1,2,3]]  # single row

assert sol.matrixRankTransform([[1],[2],[3]]) == [[1],[2],[3]]  # single column

assert sol.matrixRankTransform([[5,5,1]]) == [[2,2,1]]  # repeated values in same row

assert sol.matrixRankTransform([[1,2],[1,3]]) == [[1,2],[1,3]]  # repeated column values

assert sol.matrixRankTransform([[10,-10],[0,5]]) == [[3,1],[2,3]]  # negative values

assert sol.matrixRankTransform([[1,1],[1,2]]) == [[1,1],[1,2]]  # connected equal component

Test Summary

Test Why
[[1,2],[3,4]] Basic increasing relationships
[[7,7],[7,7]] All values equal
Complex example from prompt Tests multiple connected equal groups
[[1]] Smallest possible matrix
Single row Verifies row-only ordering
Single column Verifies column-only ordering
Repeated values in row Ensures equal ranks
Repeated values in column Ensures column consistency
Negative values Confirms sorting handles negatives
Connected equal component Tests Union-Find grouping

Edge Cases

All Values Equal

When every cell contains the same value, every cell must receive the same rank. A buggy implementation might incorrectly assign increasing ranks while scanning rows or columns sequentially. The Union-Find grouping prevents this by merging all connected equal-value cells into one component and assigning them a single shared rank.

Equal Values Connected Indirectly

Consider:

1 2 2
2 2 3

Some equal values are not directly adjacent but become connected through shared rows and columns. A naive implementation that only checks immediate neighbors could assign inconsistent ranks. The Union-Find structure correctly merges all connected equal-value cells into the same component.

Updating Ranks Too Early

Suppose several equal-value cells are being processed together. If row and column ranks are updated immediately after each cell, later cells of the same value may incorrectly see inflated dependencies and receive ranks that are too large. The implementation avoids this by storing updates temporarily and applying them only after all groups for the current value have been processed.