# Rank Transform of a Matrix
**Difficulty:** HARD
[External](https://leetcode.com/problems/rank-transform-of-a-matrix)
Canonical: https://scaleengineer.com/dsa/problems/rank-transform-of-a-matrix
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Union Find](https://scaleengineer.com/algorithms/union-find), [Topological Sort](https://scaleengineer.com/algorithms/topological-sort)
**Data structures:** Array, Matrix, Graph
**Companies:** [Citadel](https://scaleengineer.com/companies/citadel)
---
## 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. It is calculated using the following rules:

* The rank is an integer starting from `1`.
* If two elements `p` and `q` are in the **same row or column**, then:  
  * If `p < q` then `rank(p) < rank(q)`
  * If `p == q` then `rank(p) == rank(q)`
  * If `p > q` then `rank(p) > rank(q)`
* The **rank** should be as **small** as possible.

The test cases are generated so that `answer` is unique under the given rules.

**Example 1:**

![](https://assets.glich.co/dsa/rank-transform-of-a-matrix/image0.jpg) 

**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.
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:**

![](https://assets.glich.co/dsa/rank-transform-of-a-matrix/image1.jpg) 

**Input:** matrix = [[7,7],[7,7]]
**Output:** [[1,1],[1,1]]

**Example 3:**

![](https://assets.glich.co/dsa/rank-transform-of-a-matrix/image2.jpg) 

**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]]

**Constraints:**

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

# Approaches
## Topological Sort on a Component Graph
This approach models the problem as finding the longest path in a Directed Acyclic Graph (DAG). First, we identify groups of cells that must have the same rank. These are cells with the same value that are connected by being in the same row or column. We can find these groups, or "components," using a Union-Find data structure.

Once components are identified, we build a dependency graph where each node is a component. A directed edge exists from component `C_a` to `C_b` if an element in `C_b` is in the same row or column as an element in `C_a`, and `value(C_b) > value(C_a)`. This implies `rank(C_b)` must be greater than `rank(C_a)`.

The rank of a component is then `1 +` the maximum rank of its predecessors in this graph. This is a classic longest path problem in a DAG, which can be solved efficiently using topological sorting. We process components with no dependencies first (rank 1), then their successors, and so on, propagating the ranks through the graph.
**Time:** O(m*n * (log m + log n))
*   Finding components with Union-Find: `O(m*n * α(m*n))`, where `α` is the inverse Ackermann function.
*   Building the graph: Iterating through all rows and columns and sorting the components within them takes `O(m * n log n + n * m log m) = O(m*n * (log m + log n))`, which is the dominant step.
*   Topological sort: `O(V + E)`, where `V` (vertices) and `E` (edges) are at most `O(m*n)`. This is `O(m*n)`. · **Space:** O(m*n)
*   Union-Find data structure: `O(m*n)`.
*   Component graph (adjacency list): `O(m*n)`.
*   Auxiliary arrays for ranks and in-degrees: `O(m*n)`.
*   Result matrix: `O(m*n)`.
**Pros:** It's a conceptually clear way to model the rank dependencies as a graph problem.; Correctly handles all constraints of the problem by explicitly building and solving the dependency graph.
**Cons:** More complex to implement compared to the value-sorting approach.; Building the explicit component graph can have significant overhead in terms of both time and space, potentially making it slower in practice despite similar asymptotic complexity.
### Explanation
The algorithm consists of four main steps:
1.  **Identify Components:** We group cells that must have the same rank. Two cells `(r1, c1)` and `(r2, c2)` must have the same rank if `matrix[r1][c1] == matrix[r2][c2]` and they are in the same row or column. This relationship is transitive. We can use a Union-Find data structure over all `m*n` cells to find these components. We iterate through the matrix, grouping cells by value. For each group of cells with the same value, we union them if they share a row or column.

2.  **Build Component Graph:** We construct a directed graph where nodes represent the components found in the previous step. We iterate through each row and each column of the matrix. For each row (or column), we find the distinct components present. We sort these components based on their corresponding matrix values. Then, for each adjacent pair of components `C_a` and `C_b` in the sorted list (where `value(C_a) < value(C_b)`), we add a directed edge from `C_a` to `C_b`. This signifies that `rank(C_b)` depends on `rank(C_a)`. We also maintain an in-degree count for each component node.

3.  **Calculate Ranks via Topological Sort:** With the component graph and in-degrees, we can find the ranks. The rank of a component is the length of the longest path from a source node (in-degree 0) to it.
    *   Initialize a queue with all components that have an in-degree of 0.
    *   Initialize the rank of all components to 1.
    *   While the queue is not empty, dequeue a component `C_u`. For each of its neighbors `C_v`, we update `rank[C_v] = max(rank[C_v], rank[C_u] + 1)`. Then, we decrement the in-degree of `C_v`. If its in-degree becomes 0, we add it to the queue.

4.  **Construct the Result Matrix:** After computing the rank for every component, we create the final `answer` matrix. For each cell `(r, c)`, we find the root of its component using the Union-Find structure and assign the computed rank of that component to `answer[r][c]`.
### Algorithm
*   Initialize a Union-Find data structure for all `m * n` cells.
*   Group cells by their value. For each value, iterate through its cells and `union` any two that are in the same row or column. This identifies components of cells that must have the same rank.
*   Create an adjacency list and an in-degree array for a new graph where nodes are the components found.
*   Build the graph: For each row, get the list of unique components, sort them by their matrix value, and add directed edges `C_i -> C_{i+1}` between components with increasing values. Update the in-degree of the destination node. Repeat for all columns.
*   Initialize a queue with all component nodes that have an in-degree of 0. Initialize ranks for all components to 1.
*   Perform a topological sort. While the queue is not empty, dequeue a component `u`. For each neighbor `v` of `u`, update `rank[v] = max(rank[v], rank[u] + 1)` and decrement `in_degree[v]`. If `in_degree[v]` becomes 0, enqueue `v`.
*   Finally, populate the `answer` matrix by assigning each cell the computed rank of its component.

## Sorting by Value with Union-Find
This is a more direct and efficient approach. The key insight is that the rank of an element depends only on the ranks of smaller elements. This suggests that we should process elements in increasing order of their values.

We first gather all cell coordinates and their values, then sort them based on the values. We iterate through the sorted list, processing all cells with the same value in a single batch.

For each batch of cells with the same value, say `v`:
1.  These cells might need to have the same rank if they are connected (i.e., share a row or column, possibly transitively). We use a Union-Find data structure to group these connected cells.
2.  The rank for any cell `(r, c)` in this batch must be at least `1` plus the maximum rank already assigned in its row `r` and column `c`. We find this potential rank for each cell.
3.  All cells in a connected component (found via Union-Find) must have the same rank. This rank must be the maximum of all their individual potential ranks to satisfy all constraints.
4.  After determining the rank for each component, we assign it to all cells within that component and update the maximum rank seen so far for their respective rows and columns. This prepares the state for processing the next batch of cells with a larger value.
**Time:** O(m*n * log(m*n))
*   Populating the `TreeMap`: `O(m*n * log D)`, where `D` is the number of distinct values. If we sort a list of all points, it's `O(m*n * log(m*n))`, which is the bottleneck.
*   Processing all points: The main loop iterates through each point. The Union-Find operations for a batch of size `k` take `O(k * α(k))`. Summing over all batches, the total is `O(m*n * α(m*n))`. · **Space:** O(m*n)
*   The `TreeMap` or a sorted list of points: `O(m*n)`.
*   `rankRow`, `rankCol` arrays: `O(m+n)`.
*   Union-Find structure for the largest batch: In the worst case, all cells have the same value, so `O(m*n)`.
*   Result matrix: `O(m*n)`.
**Pros:** Highly efficient and directly solves the problem by respecting rank dependencies.; Simpler to implement than the explicit graph-based approach.; Avoids building a large, explicit graph structure, which reduces constant factors and memory overhead.
**Cons:** Requires careful handling of indices and data structures for the Union-Find within each batch.
### Explanation
The algorithm proceeds as follows:
1.  **Group and Sort:** Create a data structure to hold the coordinates of cells grouped by their value. A `TreeMap<Integer, List<int[]>>` is ideal as it automatically keeps the values sorted. We populate this map by iterating through the input `matrix`.

2.  **Initialize Rank Tracking:** Create two arrays, `rankRow` of size `m` and `rankCol` of size `n`, to store the latest (and thus maximum) rank assigned in each row and column. Initialize them to all zeros. The final `answer` matrix is also initialized.

3.  **Process Batches by Value:** Iterate through the `TreeMap`. For each value `v` and its corresponding list of coordinates `coords`:
    a. **Union-Find for the Batch:** Create a new Union-Find structure just for the cells in the current batch `coords`. We can map each cell `(r, c)` to its index in the `coords` list.
    b. **Connect Cells:** Group the cells in `coords` by their row and column. For all cells in the same row, union them together. Do the same for all cells in the same column. This efficiently finds all connected components of cells with value `v`.
    c. **Group Components:** After connecting cells, group them into components. A `Map<Integer, List<Integer>>` can be used, mapping a component's root (from Union-Find) to a list of indices of cells belonging to it.
    d. **Calculate Ranks and Update:**
        i. Iterate through each component (each entry in the map from the previous step).
        ii. For a given component, find the maximum required rank. This is done by iterating through all cells in the component, and for each cell `(r, c)`, finding `max(rankRow[r], rankCol[c])`. The maximum of these values over the entire component is found. Let's call it `baseRank`.
        iii. The final rank for all cells in this component is `baseRank + 1`.
        iv. Assign this `finalRank` to the `answer` matrix for all cells in the current component.
    e. **Update Rank Trackers:** After all components for the current value `v` have been ranked, iterate through all `coords` one last time. For each cell `(r, c)`, update `rankRow[r] = answer[r][c]` and `rankCol[c] = answer[r][c]`. This prepares the trackers for the next, larger value.

```java
import java.util.*;

class Solution {
    public int[][] matrixRankTransform(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        
        // Group coordinates by value
        TreeMap<Integer, List<int[]>> valueToCoords = new TreeMap<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                valueToCoords.computeIfAbsent(matrix[i][j], k -> new ArrayList<>()).add(new int[]{i, j});
            }
        }
        
        int[][] answer = new int[m][n];
        int[] rankRow = new int[m]; // Stores the max rank in each row
        int[] rankCol = new int[n]; // Stores the max rank in each col
        
        for (int value : valueToCoords.keySet()) {
            List<int[]> coords = valueToCoords.get(value);
            int size = coords.size();
            UnionFind uf = new UnionFind(size);
            
            // Union cells in the same row/column
            Map<Integer, Integer> rowToIdx = new HashMap<>();
            Map<Integer, Integer> colToIdx = new HashMap<>();
            for (int i = 0; i < size; i++) {
                int r = coords.get(i)[0];
                int c = coords.get(i)[1];
                if (rowToIdx.containsKey(r)) {
                    uf.union(i, rowToIdx.get(r));
                } else {
                    rowToIdx.put(r, i);
                }
                if (colToIdx.containsKey(c)) {
                    uf.union(i, colToIdx.get(c));
                } else {
                    colToIdx.put(c, i);
                }
            }
            
            // Group components and find max rank for each component
            Map<Integer, List<Integer>> components = new HashMap<>();
            for (int i = 0; i < size; i++) {
                int root = uf.find(i);
                components.computeIfAbsent(root, k -> new ArrayList<>()).add(i);
            }
            
            for (List<Integer> componentIndices : components.values()) {
                int maxRank = 0;
                for (int idx : componentIndices) {
                    int r = coords.get(idx)[0];
                    int c = coords.get(idx)[1];
                    maxRank = Math.max(maxRank, Math.max(rankRow[r], rankCol[c]));
                }
                int finalRank = maxRank + 1;
                for (int idx : componentIndices) {
                    int r = coords.get(idx)[0];
                    int c = coords.get(idx)[1];
                    answer[r][c] = finalRank;
                }
            }

            // Update rankRow and rankCol for the next iteration
            for (int[] coord : coords) {
                int r = coord[0];
                int c = coord[1];
                rankRow[r] = answer[r][c];
                rankCol[c] = answer[r][c];
            }
        }
        
        return answer;
    }

    private static class UnionFind {
        private int[] parent;
        
        public UnionFind(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }
        
        public int find(int i) {
            if (parent[i] == i) {
                return i;
            }
            parent[i] = find(parent[i]);
            return parent[i];
        }
        
        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                parent[rootI] = rootJ;
            }
        }
    }
}
```
### Algorithm
*   Create a `TreeMap<Integer, List<int[]>>` to store cell coordinates, grouped and sorted by value.
*   Populate the map from the input `matrix`.
*   Initialize `rankRow[m]` and `rankCol[n]` arrays with zeros to track the maximum rank in each row and column.
*   Initialize the `answer[m][n]` matrix.
*   Iterate through each value `v` and its list of coordinates `coords` in the `TreeMap`:
    *   Initialize a Union-Find structure for the `coords.size()` elements.
    *   Use maps to group coordinates by row and column, and perform `union` operations to connect cells within the same row or column.
    *   Group the connected cells into components.
    *   For each component:
        *   Calculate the required rank by finding the maximum of `max(rankRow[r], rankCol[c])` over all cells `(r,c)` in the component. The component's rank will be this maximum value + 1.
        *   Assign this calculated rank to all cells of the component in the `answer` matrix.
    *   After ranking all cells for the current value, update `rankRow` and `rankCol` with these new ranks to be used for the next larger value.
*   Return the `answer` matrix.

# Solutions
### Java

```java
class UnionFind { private int [] p ; private int [] size ; public UnionFind ( int n ) { p = new int [ n ]; size = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { p [ i ] = i ; size [ i ] = 1 ; } } public int find ( int x ) { if ( p [ x ] != x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; } public void union ( int a , int b ) { int pa = find ( a ), pb = find ( b ); if ( pa != pb ) { if ( size [ pa ] > size [ pb ]) { p [ pb ] = pa ; size [ pa ] += size [ pb ]; } else { p [ pa ] = pb ; size [ pb ] += size [ pa ]; } } } public void reset ( int x ) { p [ x ] = x ; size [ x ] = 1 ; } } class Solution { public int [][] matrixRankTransform ( int [][] matrix ) { int m = matrix . length , n = matrix [ 0 ]. length ; TreeMap < Integer , List < int []>> d = new TreeMap <>(); for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { d . computeIfAbsent ( matrix [ i ][ j ], k -> new ArrayList <>()). add ( new int [] { i , j }); } } int [] rowMax = new int [ m ]; int [] colMax = new int [ n ]; int [][] ans = new int [ m ][ n ]; UnionFind uf = new UnionFind ( m + n ); int [] rank = new int [ m + n ]; for ( var ps : d . values ()) { for ( var p : ps ) { uf . union ( p [ 0 ], p [ 1 ] + m ); } for ( var p : ps ) { int i = p [ 0 ], j = p [ 1 ]; rank [ uf . find ( i )] = Math . max ( rank [ uf . find ( i )], Math . max ( rowMax [ i ], colMax [ j ])); } for ( var p : ps ) { int i = p [ 0 ], j = p [ 1 ]; ans [ i ][ j ] = 1 + rank [ uf . find ( i )]; rowMax [ i ] = ans [ i ][ j ]; colMax [ j ] = ans [ i ][ j ]; } for ( var p : ps ) { uf . reset ( p [ 0 ]); uf . reset ( p [ 1 ] + m ); } } return ans ; } }
```

### CPP

```cpp
class UnionFind { public: UnionFind ( int n ) { p = vector < int > ( n ); size = vector < int > ( n , 1 ); iota ( p . begin (), p . end (), 0 ); } void unite ( int a , int b ) { int pa = find ( a ), pb = find ( b ); if ( pa != pb ) { if ( size [ pa ] > size [ pb ]) { p [ pb ] = pa ; size [ pa ] += size [ pb ]; } else { p [ pa ] = pb ; size [ pb ] += size [ pa ]; } } } int find ( int x ) { if ( p [ x ] != x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; } void reset ( int x ) { p [ x ] = x ; size [ x ] = 1 ; } private: vector < int > p , size ; }; class Solution { public: vector < vector < int >> matrixRankTransform ( vector < vector < int >>& matrix ) { int m = matrix . size (), n = matrix [ 0 ]. size (); map < int , vector < pair < int , int >>> d ; for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { d [ matrix [ i ][ j ]]. push_back ({ i , j }); } } vector < int > rowMax ( m ); vector < int > colMax ( n ); vector < vector < int >> ans ( m , vector < int > ( n )); UnionFind uf ( m + n ); vector < int > rank ( m + n ); for ( auto & [ _ , ps ] : d ) { for ( auto & [ i , j ] : ps ) { uf . unite ( i , j + m ); } for ( auto & [ i , j ] : ps ) { rank [ uf . find ( i )] = max ({ rank [ uf . find ( i )], rowMax [ i ], colMax [ j ]}); } for ( auto & [ i , j ] : ps ) { ans [ i ][ j ] = rowMax [ i ] = colMax [ j ] = 1 + rank [ uf . find ( i )]; } for ( auto & [ i , j ] : ps ) { uf . reset ( i ); uf . reset ( j + m ); } } return ans ; } };
```

### Python

```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
```