Rank Transform of a Matrix

Hard

#1500Time: 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)`.1 company

Algorithms

Sorting Union Find Topological Sort

Data structures

Array Matrix Graph

Companies

Citadel

Prompt

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:

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:

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

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

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

The algorithm consists of four main steps:

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

Complexity

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

Trade-offs

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.

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:

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

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.

Walkthrough

The algorithm proceeds as follows:

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

1import java.util.*;2 3class Solution {4    public int[][] matrixRankTransform(int[][] matrix) {5        int m = matrix.length;6        int n = matrix[0].length;7        8        // Group coordinates by value9        TreeMap<Integer, List<int[]>> valueToCoords = new TreeMap<>();10        for (int i = 0; i < m; i++) {11            for (int j = 0; j < n; j++) {12                valueToCoords.computeIfAbsent(matrix[i][j], k -> new ArrayList<>()).add(new int[]{i, j});13            }14        }15        16        int[][] answer = new int[m][n];17        int[] rankRow = new int[m]; // Stores the max rank in each row18        int[] rankCol = new int[n]; // Stores the max rank in each col19        20        for (int value : valueToCoords.keySet()) {21            List<int[]> coords = valueToCoords.get(value);22            int size = coords.size();23            UnionFind uf = new UnionFind(size);24            25            // Union cells in the same row/column26            Map<Integer, Integer> rowToIdx = new HashMap<>();27            Map<Integer, Integer> colToIdx = new HashMap<>();28            for (int i = 0; i < size; i++) {29                int r = coords.get(i)[0];30                int c = coords.get(i)[1];31                if (rowToIdx.containsKey(r)) {32                    uf.union(i, rowToIdx.get(r));33                } else {34                    rowToIdx.put(r, i);35                }36                if (colToIdx.containsKey(c)) {37                    uf.union(i, colToIdx.get(c));38                } else {39                    colToIdx.put(c, i);40                }41            }42            43            // Group components and find max rank for each component44            Map<Integer, List<Integer>> components = new HashMap<>();45            for (int i = 0; i < size; i++) {46                int root = uf.find(i);47                components.computeIfAbsent(root, k -> new ArrayList<>()).add(i);48            }49            50            for (List<Integer> componentIndices : components.values()) {51                int maxRank = 0;52                for (int idx : componentIndices) {53                    int r = coords.get(idx)[0];54                    int c = coords.get(idx)[1];55                    maxRank = Math.max(maxRank, Math.max(rankRow[r], rankCol[c]));56                }57                int finalRank = maxRank + 1;58                for (int idx : componentIndices) {59                    int r = coords.get(idx)[0];60                    int c = coords.get(idx)[1];61                    answer[r][c] = finalRank;62                }63            }64 65            // Update rankRow and rankCol for the next iteration66            for (int[] coord : coords) {67                int r = coord[0];68                int c = coord[1];69                rankRow[r] = answer[r][c];70                rankCol[c] = answer[r][c];71            }72        }73        74        return answer;75    }76 77    private static class UnionFind {78        private int[] parent;79        80        public UnionFind(int n) {81            parent = new int[n];82            for (int i = 0; i < n; i++) {83                parent[i] = i;84            }85        }86        87        public int find(int i) {88            if (parent[i] == i) {89                return i;90            }91            parent[i] = find(parent[i]);92            return parent[i];93        }94        95        public void union(int i, int j) {96            int rootI = find(i);97            int rootJ = find(j);98            if (rootI != rootJ) {99                parent[rootI] = rootJ;100            }101        }102    }103}

Complexity

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

Trade-offs

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.

Solutions

Solution

1class 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 ; } }

1class 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 ; } };

1class 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem