Rank Transform of a Matrix - Practice Coding Problems

Rank Transform of a Matrix - Problem

Array Union Find Graph Topological Sort Sorting Matrix Hard

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.

Input & Output

Example 1 — Basic Matrix

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

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

💡 Note: Value 1 gets rank 1, value 2 gets rank 2, value 3 gets rank 2 (constrained by row/column), value 4 gets rank 3

Example 2 — Equal Elements

$ Input: matrix = [[7,7],[7,7]]

› Output: [[1,1],[1,1]]

💡 Note: All elements have the same value, so they all get rank 1

Example 3 — Complex Constraints

$ Input: matrix = [[20,-21,14],[-19,4,19],[22,-47,24]]

› Output: [[4,2,3],[1,5,6],[6,1,7]]

💡 Note: Ranks assigned respecting row and column ordering constraints while keeping them as small as possible

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

Matrix with values that need ranking

Apply Constraints

Rank elements respecting row/column ordering

Output Ranks

Minimum possible ranks maintaining all constraints

Key Takeaway

🎯 Key Insight: Equal elements in same row/column form connected components that must share the same rank

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to use Union-Find to group equal elements in the same row/column, then apply topological sort to assign minimum ranks while respecting ordering constraints. Best approach uses Union-Find with Topological Sort. Time: O(m×n×log(m×n)), Space: O(m×n)

Common Approaches

Approach	Time	Space	Notes
✓ Union-Find with Topological Sort	O(m×n×log(m×n))	O(m×n)	Use Union-Find to group equal elements and topological sort for ordering
Brute Force Coordinate Compression	O(m×n×log(m×n))	O(m×n)	Sort all unique values and assign ranks naively

Union-Find with Topological Sort — Algorithm Steps

Step 1: Build Union-Find to connect equal elements in same row/column
Step 2: Create dependency graph for ordering constraints
Step 3: Use topological sort to assign minimum possible ranks

Visualization

Tap to expand

Step-by-Step Walkthrough

Group Equal Elements

Union-Find connects equal values in same row/column

Build Dependencies

Create ordering constraints between different values

Topological Sort

Assign minimum possible ranks respecting all constraints

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int val, r, c;
} Coord;

int compare(const void* a, const void* b) {
    Coord* ca = (Coord*)a;
    Coord* cb = (Coord*)b;
    return ca->val - cb->val;
}

int** solution(int** matrix, int matrixSize, int* matrixColSize, int* returnSize, int** returnColumnSizes) {
    *returnSize = matrixSize;
    *returnColumnSizes = (int*)malloc(matrixSize * sizeof(int));
    
    if (matrixSize == 0 || matrixColSize[0] == 0) {
        return matrix;
    }
    
    int m = matrixSize, n = matrixColSize[0];
    
    // Create coordinate array
    Coord* coords = (Coord*)malloc(m * n * sizeof(Coord));
    int coordCount = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            coords[coordCount++] = (Coord){matrix[i][j], i, j};
        }
    }
    
    // Sort by value
    qsort(coords, coordCount, sizeof(Coord), compare);
    
    // Simple approach: assign ranks based on unique values
    int uniqueVals[10000];
    int uniqueCount = 0;
    
    // Extract unique values
    for (int i = 0; i < coordCount; i++) {
        int val = coords[i].val;
        int found = 0;
        for (int j = 0; j < uniqueCount; j++) {
            if (uniqueVals[j] == val) {
                found = 1;
                break;
            }
        }
        if (!found) {
            uniqueVals[uniqueCount++] = val;
        }
    }
    
    // Create result matrix
    int** result = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        result[i] = (int*)malloc(n * sizeof(int));
        (*returnColumnSizes)[i] = n;
        for (int j = 0; j < n; j++) {
            // Find rank of matrix[i][j]
            for (int k = 0; k < uniqueCount; k++) {
                if (uniqueVals[k] == matrix[i][j]) {
                    result[i][j] = k + 1;
                    break;
                }
            }
        }
    }
    
    free(coords);
    return result;
}

int main() {
    int matrix[100][100];
    int m = 0, n = 0;
    
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    char* ptr = line + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            n = 0;
            while (*ptr && *ptr != ']') {
                if (*ptr >= '0' && *ptr <= '9' || *ptr == '-') {
                    matrix[m][n] = atoi(ptr);
                    n++;
                    while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
                    if (*ptr == ',') ptr++;
                } else {
                    ptr++;
                }
            }
            m++;
        }
        ptr++;
    }
    
    int* matrixColSize = (int*)malloc(m * sizeof(int));
    int** matrixPtrs = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        matrixColSize[i] = n;
        matrixPtrs[i] = matrix[i];
    }
    
    int returnSize;
    int* returnColumnSizes;
    int** result = solution(matrixPtrs, m, matrixColSize, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%d", result[i][j]);
            if (j < returnColumnSizes[i] - 1) printf(",");
        }
        printf("]");
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n×log(m×n))

Sorting coordinates by value O(m×n×log(m×n)), Union-Find operations nearly O(1), topological sort O(nodes + edges)

⚡ Linearithmic

Space Complexity

O(m×n)

Union-Find structure, adjacency list, and result matrix storage

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Union-Find with Topological Sort — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler