How to Solve Rank Transform of a Matrix

Start by sorting all cells by their values and use Union Find to group elements that must share ranks. Then build a graph representing dependencies between elements in rows and columns. Finally, apply topological sorting to assign ranks while maintaining uniqueness and correct ordering across the matrix.

Problem Statement

Given an m x n matrix, return a new matrix answer where each answer[row][col] represents the rank of matrix[row][col]. The rank is the smallest integer that satisfies the ordering rules across both rows and columns.

The rank of an element is calculated such that it is strictly greater than any smaller elements in the same row or column. Equal elements in the same row or column may share ranks. The input guarantees that the resulting rank matrix is unique under these constraints.

Examples

Example 1

Input: matrix = [[1,2],[3,4]]

Output: [[1,2],[2,3]]

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

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

Example details omitted.

Constraints

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

Solution Approach

Sort and Group Equal Elements

Flatten the matrix and sort cells by value. Use Union Find to link elements that are equal and must share the same rank, ensuring that dependencies in rows and columns are maintained.

Build Dependency Graph

For each row and column, create directed edges from smaller ranks to larger ones. This captures the required ordering constraints as a graph, ready for topological sorting to assign consistent ranks.

Assign Ranks via Topological Sort

Perform a topological sort on the graph, assigning ranks starting from 1 and incrementing along dependencies. Union Find ensures tied elements are assigned identical ranks while respecting row and column constraints.

Complexity Analysis

Time complexity is dominated by sorting cells O(mnlog(mn)) and graph processing. Space complexity depends on storing parent arrays for Union Find and adjacency lists for topological sorting, typically O(mn).

What Interviewers Usually Probe

• Watch for correctly linking equal elements to avoid rank conflicts.
• Check for proper graph edge creation between dependent elements in rows and columns.
• Ensure topological sort respects both row and column ordering constraints to maintain uniqueness.

Common Pitfalls or Variants

Common pitfalls

• Failing to merge equal elements before building dependencies, causing incorrect rank assignments.
• Ignoring column or row constraints when adding graph edges, leading to invalid topological ordering.
• Assuming ranks can be assigned greedily without topological sorting, which breaks uniqueness in some matrices.

Follow-up variants

• Apply the same approach to a 1D array to assign relative ranks respecting duplicates.
• Compute ranks only for a single row or column subset while maintaining graph indegree ordering.
• Use the algorithm for sparse matrices where most entries are zero, optimizing Union Find and graph storage.

How GhostInterview Helps

• GhostInterview highlights where Union Find must merge equal elements before rank assignment.
• It visualizes row and column dependencies as a graph to clarify topological ordering steps.
• The solver flags common pitfalls like ignoring constraints or assigning ranks too early, ensuring correctness.

Topic Pages

• Array
• Union Find
• Graph
• Topological Sort
• Sorting
• Matrix

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What pattern does Rank Transform of a Matrix rely on?

It relies on graph indegree plus topological ordering to assign ranks uniquely while respecting row and column dependencies.

Can equal elements in the same row or column have different ranks?

No, equal elements must share the same rank and be merged using Union Find before rank assignment.

What is the main time complexity factor in this problem?

Sorting the cells by value dominates the time complexity, followed by graph construction and topological sorting.

How do I handle large matrices efficiently?

Use Union Find for grouping equal elements and sparse adjacency lists for graph edges to reduce overhead.

Why is topological sorting necessary for assigning ranks?

Topological sorting ensures that every element’s rank is larger than all smaller elements in the same row or column, maintaining uniqueness.