The problem

Rank Transform of a 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.

It is guaranteed that answer is unique under the given rules.

 

Example 1:

Input: matrix = [[1, 2], [3, 4]] Output: [[1, 2], [2, 3]] Explanation: 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.Copy the code

Example 2:

Input: matrix = [[7, 7], [7, 7]] Output: [[1, 1], [1, 1]]Copy the code

Example 3:

Input: matrix = [[20, 21, 14], [- 19,4,19], [22, - 47, 24], [- 19,4,19]] Output: [[4, 2, 3], [4] 1,,1,6 [5], [1 4]]Copy the code

Example 4:

Input: matrix = [,3,6 [7],].enlighened by,8,2 [9]] Output: [,1,4 [5], [1, 2, 3], [6,3,1]]Copy the code

 

Constraints:

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

Hint 1

Sort the cells by value and process them in increasing order.

Hint 2

The rank of a cell is the maximum rank in its row and column plus one.

Hint 3

Handle the equal cells by treating them as components using a union-find data structure.

Their thinking

The question seems simple, but in fact it is a difficult one. What is calculated is the rank of the matrix, commonly known as the rank, and the difficulty lies in:

  1. The positions in a row affect each other, for examplepIt ranks first in the line3But at the top of the list4, so the final ranking is4
  2. Nodes with the same value in the same column must have the same rank, which affects the rank of multiple rows and columns, for example[3, 2], [3, 4], [5, 4]The value of the node is the same, then the3Ok, the first5Ok, the first2The column, the first4The columnThe rankings affect each other

Fortunately, LeetCode has prepared three tricks for us to take apart as clues to solve the problem.

Hint 1

Sort the cells by value and process them in increasing order.

The first trick is to sort all the nodes and process them from smallest to largest. The advantage of this is that the smaller nodes treated earlier are no longer affected by the later nodes. We can convert each node to a data structure or array, such as int[3], where [0] represents the value of the node, [1] represents the row, and [2] represents the column. The entire matrix can be converted to int[][] arr = new int[m*n][3]. So you sort it, and then you sort it from the smallest to the largest.

Hint 2

The rank of a cell is the maximum rank in its row and column plus one.

The second tip is to record the maximum rank of the current row and column in the order described above. The corresponding node rank is the largest of the maximum rank of the current row and column +1. Of course, after processing, the rank of this node should also be used as the maximum rank of the corresponding row. We can use int[] currRankRows and int[] currRankCols to record the current maximum rank of all rows.

Hint 3

Handle the equal cells by treating them as components using a union-find data structure.

The third trick is to let us use a look-up set to deal with same-valued nodes. Parallel lookup sets are considered to be one of the most concise and elegant data structures, mainly used to solve some problems of grouping elements. It manages a series of disjoint collections and supports two operations:

  • Union: To combine two disjoint sets into a single set.
  • Find: Queries whether two elements are in the same collection.

This tip can be used to solve the problem we mentioned earlier, which is how to deal with the interaction between rows and columns. We can treat rows and columns as elements of the same class, place rows and columns affected by nodes of the same value in the same group, and then unify the ranks within the group (because nodes of the same value in the same row must be in the same order). So we define FFF as a union set, with x for a row or a column. For a matrix element matrix[I][j], when x represents a row, x = I; When x represents columns, x = m + j, where m is the total number of rows in the matrix. By the definition of the set, f(x)f(x)f(x) refers to the parent node of X, while f(x)=xf(x)=xf(x)=x for the root node.

Refer to the answer


class Solution {

    int[] f; // union-find set

    public int[][] matrixRankTransform(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        int[][] ret = new int[m][n];

        int[] currRankRows = new int[m];
        int[] currRankCols = new int[n];

        // initial union-find data structure, contains all the rows & cols, the length is m + n
        int[] initF = new int[m + n];
        for (int i = 0; i < m + n; i++) {
            initF[i] = i;
        }

        // put all cells into an array then sort
        int[][] arr = new int[m*n][3];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                arr[i*n+j][0] = matrix[i][j];
                arr[i*n+j][1] = i;
                arr[i*n+j][2] = j;
            }
        }

        Arrays.sort(arr, Comparator.comparingInt(o->o[0]));

        int i = 0;
        // loop the array with all matrix cells
        while(i < arr.length) {
            int target = arr[i][0];
            List<int[]> equals = new ArrayList<>();

            // get cells that has same value
            while (i < arr.length && target == arr[i][0]) {
                equals.add(arr[i]);
                i++;
            }

            // Union-find data structure
            f = initF.clone();

            // union set for f(x)
            for (int[] cell : equals) {
                union(cell[1], cell[2] + m);
            }

            // if equal numbers in same row/col, then group into map by f(x), as these need to have same rank
            Map<Integer, List<int[]>> map = new HashMap<>();
            for (int[] cell : equals) {
                int k = find(cell[1]);
                if(! map.containsKey(k)) { map.put(k,new ArrayList<>());
                }
                map.get(k).add(cell);
            }

            // handle group by group
            for (List<int[]> group : map.values()) {
                // find max rank in group
                int maxRank = 0;
                for (int[] cell : group) {
                    int row = cell[1];
                    int col = cell[2];
                    maxRank = Math.max(maxRank, Math.max(currRankRows[row], currRankCols[col]) + 1);
                }
                // update max rank to current rank of rows & cols
                for (int[] cell : group) {
                    int row = cell[1];
                    int col = cell[2]; ret[row][col] = maxRank; currRankRows[row] = Math.max(currRankRows[row], maxRank); currRankCols[col] = Math.max(currRankCols[col], maxRank); }}}return ret;
    }

    int find (int x) {
        if(f[x] ! = x) { f[x] = find(f[x]); }return f[x];
    }

    void union(int x, int y) {
        int fm = find(x);
        intfn = find(y); f[fm] = fn; }}Copy the code

Expand training

Check out the author’s LeetCode column for additional questions of interest.

Juejin. Cn/column / 6997…

The data link

The original leetcode.com/problems/ra…

Check and set zh.wikipedia.org/wiki/%E5%B9…