Problem statement

Given an m x n integer matrix, return a new matrix answer where answer[row][col] is the rank of matrix[row][col].

Ranks are positive integers chosen by these rules:

• Within the same row or the same column, a smaller element gets a smaller rank, a larger element a larger rank, and equal elements the same rank: for two cells p and q that share a row or a column, p < q implies rank(p) < rank(q) and p == q implies rank(p) == rank(q).
• Every rank is as small as possible.

The rules determine the answer uniquely.

Example 1

Input: matrix = [[1,2],[3,4]]
Output: [[1,2],[2,3]]
Explanation: 1 is the smallest in its row and column (rank 1); 2 and 3 each sit beside the 1 (rank 2); 4 is larger than both 2 and 3 (rank 3).

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^9 <= matrix[row][col] <= 10^9

Hints for Rank Transform of a Matrix

1. Hint 1

   Process the values from smallest to largest. When a value is processed, its rank only depends on the largest rank already given in its row and in its column.

2. Hint 2

   Equal values in the same row or column must share a rank, and that sharing is transitive: they form groups. A union-find over rows and columns (row r and column c joined for every cell (r, c) of the current value) finds the groups.

3. Hint 3

   For each group, rank = 1 + max over its cells of max(rowMax[r], colMax[c]). Assign it to every cell of the group, then update rowMax and colMax.

How to solve Rank Transform of a Matrix

Sort cells by value and hand out ranks in increasing order, keeping the largest rank so far in every row and column. Cells of equal value that share a row or column — directly or through a chain — must receive one common rank, so they are grouped with a union-find on row and column ids.

Approach

1. Sort all cells by value. Keep rowMax[m] and colMax[n], initially 0.
2. Take the next block of cells with equal value. For each cell (r, c) in it, union node r with node m + c.
3. For each cell, fold max(rowMax[r], colMax[c]) + 1 into the value stored at its group's root.
4. Give every cell its root's value, set rowMax[r] and colMax[c] to it, then reset the union-find nodes the block touched.

Why it works

When a block is processed, every smaller value in a cell's row or column already has its final rank, and rowMax/colMax hold the largest of them, so a rank below max + 1 would violate the ordering rule. Cells joined through shared rows or columns must be equal-ranked, so the group takes the maximum of its members' lower bounds — and that value satisfies every constraint, hence it is the smallest possible.

Complexity

• Time — O(m · n · log(m · n))
• Space — O(m · n)

Pitfalls

• Equal values in different rows and columns are independent: they may get different ranks.
• Grouping is transitive: (r1, c1) and (r2, c2) with r1 ≠ r2 and c1 ≠ c2 still share a rank if a third equal cell sits in row r1 and column c2.
• Reset only the union-find nodes the current block touched; resetting everything per block is quadratic.

Reference solution

Python

from typing import List

def matrixRankTransform(matrix: List[List[int]]) -> List[List[int]]:
    m, n = len(matrix), len(matrix[0])
    cells = sorted((matrix[r][c], r, c) for r in range(m) for c in range(n))
    parent = list(range(m + n))
    best = [0] * (m + n)
    row_max = [0] * m
    col_max = [0] * n
    ans = [[0] * n for _ in range(m)]

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    i, total = 0, m * n
    while i < total:
        j = i
        while j < total and cells[j][0] == cells[i][0]:
            j += 1
        for _, r, c in cells[i:j]:
            a, b = find(r), find(m + c)
            if a != b:
                parent[a] = b
        for _, r, c in cells[i:j]:
            root = find(r)
            best[root] = max(best[root], max(row_max[r], col_max[c]) + 1)
        for _, r, c in cells[i:j]:
            ans[r][c] = best[find(r)]
        for _, r, c in cells[i:j]:
            row_max[r] = ans[r][c]
            col_max[c] = ans[r][c]
            parent[r], parent[m + c] = r, m + c
            best[r] = best[m + c] = 0
        i = j
    return ans

Java

static int[] par;

static int find(int x) {
    while (par[x] != x) { par[x] = par[par[x]]; x = par[x]; }
    return x;
}

public static int[][] matrixRankTransform(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length, total = m * n;
    final long S = 262144L;
    long[] keys = new long[total];
    for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) keys[r * n + c] = ((long) matrix[r][c] + 1000000000L) * S + r * n + c;
    Arrays.sort(keys);
    par = new int[m + n];
    int[] best = new int[m + n], rowMax = new int[m], colMax = new int[n];
    for (int i = 0; i < m + n; i++) par[i] = i;
    int[][] ans = new int[m][n];
    int lo = 0;
    while (lo < total) {
        long v = keys[lo] / S;
        int hi = lo;
        while (hi < total && keys[hi] / S == v) hi++;
        for (int k = lo; k < hi; k++) {
            int cell = (int) (keys[k] % S), x = cell / n, y = cell % n;
            int p = find(x), q = find(m + y);
            if (p != q) par[p] = q;
        }
        for (int k = lo; k < hi; k++) {
            int cell = (int) (keys[k] % S), x = cell / n, y = cell % n;
            int root = find(x);
            best[root] = Math.max(best[root], Math.max(rowMax[x], colMax[y]) + 1);
        }
        for (int k = lo; k < hi; k++) {
            int cell = (int) (keys[k] % S), x = cell / n, y = cell % n;
            ans[x][y] = best[find(x)];
        }
        for (int k = lo; k < hi; k++) {
            int cell = (int) (keys[k] % S), x = cell / n, y = cell % n;
            rowMax[x] = ans[x][y];
            colMax[y] = ans[x][y];
            par[x] = x; par[m + y] = m + y;
            best[x] = 0; best[m + y] = 0;
        }
        lo = hi;
    }
    return ans;
}

C++

vector<int> par;

int findRoot(int x) {
    while (par[x] != x) { par[x] = par[par[x]]; x = par[x]; }
    return x;
}

vector<vector<int>> matrixRankTransform(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size(), total = m * n;
    const long long S = 262144LL;
    vector<long long> keys;
    for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) keys.push_back(((long long) matrix[r][c] + 1000000000LL) * S + r * n + c);
    sort(keys.begin(), keys.end());
    par.assign(m + n, 0);
    for (int i = 0; i < m + n; i++) par[i] = i;
    vector<int> best(m + n, 0), rowMax(m, 0), colMax(n, 0);
    vector<vector<int>> ans(m, vector<int>(n, 0));
    int lo = 0;
    while (lo < total) {
        long long v = keys[lo] / S;
        int hi = lo;
        while (hi < total && keys[hi] / S == v) hi++;
        for (int k = lo; k < hi; k++) {
            int cell = keys[k] % S, x = cell / n, y = cell % n;
            int p = findRoot(x), q = findRoot(m + y);
            if (p != q) par[p] = q;
        }
        for (int k = lo; k < hi; k++) {
            int cell = keys[k] % S, x = cell / n, y = cell % n;
            int root = findRoot(x);
            best[root] = max(best[root], max(rowMax[x], colMax[y]) + 1);
        }
        for (int k = lo; k < hi; k++) {
            int cell = keys[k] % S, x = cell / n, y = cell % n;
            ans[x][y] = best[findRoot(x)];
        }
        for (int k = lo; k < hi; k++) {
            int cell = keys[k] % S, x = cell / n, y = cell % n;
            rowMax[x] = ans[x][y];
            colMax[y] = ans[x][y];
            par[x] = x; par[m + y] = m + y;
            best[x] = 0; best[m + y] = 0;
        }
        lo = hi;
    }
    return ans;
}

JavaScript

var matrixRankTransform = function(matrix) {
    var m = matrix.length, n = matrix[0].length, total = m * n, S = 262144;
    var keys = [];
    for (var r = 0; r < m; r++) for (var c = 0; c < n; c++) keys.push((matrix[r][c] + 1000000000) * S + r * n + c);
    keys.sort(function(a, b) { return a - b; });
    var parent = [], best = [], rowMax = [], colMax = [], ans = [];
    for (var i = 0; i < m + n; i++) { parent.push(i); best.push(0); }
    for (var a = 0; a < m; a++) { rowMax.push(0); ans.push([]); for (var b = 0; b < n; b++) ans[a].push(0); }
    for (var b2 = 0; b2 < n; b2++) colMax.push(0);
    var find = function(x) {
        while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    };
    var lo = 0;
    while (lo < total) {
        var v = Math.floor(keys[lo] / S), hi = lo, k, cell, x, y, root;
        while (hi < total && Math.floor(keys[hi] / S) === v) hi++;
        for (k = lo; k < hi; k++) {
            cell = keys[k] % S; x = Math.floor(cell / n); y = cell % n;
            var p = find(x), q = find(m + y);
            if (p !== q) parent[p] = q;
        }
        for (k = lo; k < hi; k++) {
            cell = keys[k] % S; x = Math.floor(cell / n); y = cell % n;
            root = find(x);
            best[root] = Math.max(best[root], Math.max(rowMax[x], colMax[y]) + 1);
        }
        for (k = lo; k < hi; k++) {
            cell = keys[k] % S; x = Math.floor(cell / n); y = cell % n;
            ans[x][y] = best[find(x)];
        }
        for (k = lo; k < hi; k++) {
            cell = keys[k] % S; x = Math.floor(cell / n); y = cell % n;
            rowMax[x] = ans[x][y];
            colMax[y] = ans[x][y];
            parent[x] = x; parent[m + y] = m + y;
            best[x] = 0; best[m + y] = 0;
        }
        lo = hi;
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard