LeetCode 1632: Rank Transform of a Matrix
LeetCode 1632 Solution 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.
LeetCode 1632 Solutions in Java, C++, Python
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];
}
}Interactive Code Editor for LeetCode 1632
Improve Your LeetCode 1632 Solution
Use the editor below to refine the provided solution for LeetCode 1632. Select a programming language and try the following:
- Add import statements if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.
Loading editor...