LeetCode 1632: Rank Transform of a Matrix Solution

Master LeetCode problem 1632 (Rank Transform of a Matrix), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1632. Rank Transform of a Matrix

Hard

Array Union Find Graph Topological Sort Sorting Matrix

Problem Explanation

Explanation

To solve this problem, we will follow these steps:

Create a mapping from each element in the matrix to its corresponding list of coordinates.
For each unique element in non-decreasing order, assign ranks to the corresponding coordinates based on their row and column relationships.
Update the matrix with the calculated ranks.

Time complexity: O(mnlog(mn)) where m is the number of rows and n is the number of columns in the matrix. Space complexity: O(mn) for the mapping and result matrix.

Solution Code

class Solution {
    public int[][] matrixRankTransform(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        
        TreeMap<Integer, List<int[]>> map = new TreeMap<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int num = matrix[i][j];
                if (!map.containsKey(num)) {
                    map.put(num, new ArrayList<>());
                }
                map.get(num).add(new int[]{i, j});
            }
        }
        
        int[] rank = new int[m + n];
        int[][] res = new int[m][n];
        
        for (int num : map.keySet()) {
            int[] parent = new int[m + n];
            Arrays.fill(parent, -1);
            int[] rankCopy = rank.clone();
            
            for (int[] coord : map.get(num)) {
                int i = coord[0];
                int j = coord[1];
                int x = find(parent, i);
                int y = find(parent, j + m);
                parent[x] = y;
                rankCopy[y] = Math.max(rankCopy[x], rankCopy[y]);
            }
            
            for (int[] coord : map.get(num)) {
                int i = coord[0];
                int j = coord[1];
                int x = find(parent, i);
                int y = find(parent, j + m);
                rank[x] = rank[y] = res[i][j] = rankCopy[x] = rankCopy[y] + 1;
            }
        }
        
        return res;
    }
    
    private int find(int[] parent, int i) {
        if (parent[i] != i) {
            parent[i] = find(parent, parent[i]);
        }
        return parent[i];
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1632 (Rank Transform of a Matrix)?

This page provides optimized solutions for LeetCode problem 1632 (Rank Transform of a Matrix) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1632 (Rank Transform of a Matrix)?

The time complexity for LeetCode 1632 (Rank Transform of a Matrix) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1632 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1632 in Java, C++, or Python.

Back to LeetCode Solutions