Vultr DocsLatest Content

Rank Transform of a Matrix

Updated on 11 July, 2025
Rank Transform of a Matrix header image

Problem Statement

In this task, we are given an m x n matrix and required to transform this matrix into a new matrix called answer. Each element in answer corresponds to the "rank" of the respective element in the original matrix.

The "rank" of an element in the matrix is a measure of how large the element is relative to other elements, and it is always a positive integer starting from 1. To determine the rank of each element:

  • Elements are compared within their respective rows and columns.
  • An element with a smaller value than another in the same row or column will have a smaller rank.
  • Elements with the same value in the same row or column will have the same rank.
  • The smallest possible ranks are assigned in ascending order starting from 1.

The challenge ensures that the resulting matrix of ranks is unique based on the provided rules.

Examples

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.

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
  • -109 <= matrix[row][col] <= 109

Approach and Intuition

To solve for the rank matrix appropriately, we can follow a structured approach:

  1. Initial Organization:

    • Sort the matrix elements alongside their indices. This step helps in systematic comparison from the least to the greatest element.

  2. Disjoint Set Union (DSU) Structure:

    • Utilize the DSU structure or a similar method to group elements that have the same value and are in the same row or column. This assists in handling the ranks of identical numbers that need to share the same rank due to their positions.

  3. Rank Assignment:

    • Begin assigning ranks starting from 1 upwards, ensuring that all rules are adhered to. Iteratively assign ranks by moving from the smallest to the largest element, adjusting based on row and column constraints.
    • As you assign ranks, always check for the rank constraints relative to other elements in the same row and column.

  4. Rank Adjustment:

    • Adjust ranks if required, to ensure that no unnecessary ranking jumps are made. For instance, if two elements are consecutive but not directly comparable via row or column, they should not skip ranks in between unless necessary.

  5. Construction of Answer Matrix:

    • Construct the new matrix answer using the ranks calculated for each element.

Example Walk-through

  • Example 1: matrix = [[1,2],[3,4]]

    • The ranking begins at the smallest element which is 1 at position (0,0) with rank 1.
    • Element 2 at (0,1) is greater and in the same row as 1, thus gets the next rank, 2.
    • Element 3 at (1,0), is greater than 1 and in a different row, also gets rank 2 as it's the next smallest value.
    • Finally, 4 at (1,1) being the largest gets the highest rank in this matrix, which is 3.

  • Example 3: matrix = [[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]]

    • This would involve more intricate comparisons, especially with the introduction of negative values. Here we use similar principles, but ensure to rank across both rows and columns, adjusting according to the given rules, leading to a rank matrix of [[4,2,3],[1,3,4],[5,1,6],[1,3,4]].

By systematically organizing, processing, and adjusting ranks based on relative values and positions, we can effectively solve this problem.

Solutions

  • C++
cpp 
class Solution {
public:
    // Finding the parent of a node
    int getParent(unordered_map<int, int> &parent, int x) {
        if (x != parent[x]) {
            parent[x] = getParent(parent, parent[x]);
        }
        return parent[x];
    }
    
    // Union function to merge two sets
    void combine(unordered_map<int, int> &parent, int x, int y) {
        if (parent.count(x) == 0) {
            parent[x] = x;
        }
        if (parent.count(y) == 0) {
            parent[y] = y;
        }
        parent[getParent(parent, x)] = getParent(parent, y);
    }
    
    vector<vector<int>> matrixRankTransform(vector<vector<int>> &matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
    
        // Union-Find data structure setup by value
        unordered_map<int, unordered_map<int, int>> parentMap;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int val = matrix[i][j];
                // Combining row and column indices
                combine(parentMap[val], i, ~j);
            }
        }
    
        // Grouping nodes by component and value
        map<int, unordered_map<int, vector<pair<int, int>>>> groups;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int val = matrix[i][j];
                int root = getParent(parentMap[val], i);
                groups[val][root].emplace_back(i, j);
            }
        }
    
        // Result matrix initialization
        vector<vector<int>> ranks(rows, vector<int>(cols));
        vector<int> maxRowRank(rows);
        vector<int> maxColRank(cols);
        for (const auto& group : groups) {
            for (const auto& component : group.second) {
                const auto& points = component.second;
                int maxRank = 1;
                // Determine the maximum rank in the current component
                for (const auto& p : points) {
                    maxRank = max(maxRank, max(maxRowRank[p.first], maxColRank[p.second]) + 1);
                }
                // Assign rank and update row and column maximums
                for (const auto& p : points) {
                    ranks[p.first][p.second] = maxRank;
                    maxRowRank[p.first] = max(maxRowRank[p.first], maxRank);
                    maxColRank[p.second] = max(maxColRank[p.second], maxRank);
                }
            }
        }
        return ranks;
    }
};

In the provided code, you will find a C++ solution to the problem of rank transforming a matrix. This solution utilizes the Union-Find algorithm to efficiently identify and merge cells of the matrix based on their values and physical locations (i.e., row and column indices).

Key Components of the Code:

  • Union-Find Data Structure: Implements a union-find (or disjoint set) to keep track of and merge sets of matrix cells. Specifically, it has methods:

    • getParent, to locate the root of a set containing a particular element, compressing paths as it searches.
    • combine, to union two sets together, ensuring elements share a common root if they are connected.

  • Matrix Analysis and Grouping:

    • The code processes each cell in the matrix and applies the combine function to group them based on their values using the union-find structure.
    • The groups are then organized per unique values of the matrix, with each group containing all matrix cells sharing the same value.

  • Rank Assignment:

    • Initializes vectors maxRowRank and maxColRank to keep track of the maximum rank of any element in each row and column, respectively.
    • Iterates over each group, calculates the maximum rank needed for cells within that group based on their row and column, and updates their ranks accordingly.

How the Code Operates:

  1. Setting Up Union-Find by Value: The code initializes a parentMap where each cell's value is associated with a union-find structure for merging the rows and columns (cells).

  2. Node Grouping According to Components: It organizes cells into groups based on their connected components. Each group corresponds to a set of matrix cells that should be assigned the same rank.

  3. Calculating and Assigning Ranks: Using previously determined maximum ranks for rows and columns, the code calculates an appropriate rank for each component. It then assigns this rank and updates the maximal ranks for potential future components.

  4. Result Construction: Constructs the result matrix called ranks which is populated based on the ranks assigned to each cell component group.

By utilizing cross-linked structures and grouping mechanisms, this solution provides an optimized approach to rank transforming a matrix, efficiently handling large data sets with repeated values and interconnected components.

  • Java
java 
class Transformer {
    // methods renamed to findGroup and joinGroup
    public int findGroup(Map<Integer, Integer> groupMapper, int element) {
        if (element != groupMapper.get(element)) {
            groupMapper.put(element, findGroup(groupMapper, groupMapper.get(element)));
        }
        return groupMapper.get(element);
    }
    
    public void joinGroup(Map<Integer, Integer> groupMapper, int element1, int element2) {
        if (!groupMapper.containsKey(element1)) {
            groupMapper.put(element1, element1);
        }
        if (!groupMapper.containsKey(element2)) {
            groupMapper.put(element2, element2);
        }
        groupMapper.put(findGroup(groupMapper, element1), findGroup(groupMapper, element2));
    }
    
    public int[][] rankTransformation(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
    
        // create maps for the union-find structures
        Map<Integer, Map<Integer, Integer>> unionFinds = new HashMap<>();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int val = grid[i][j];
                if (!unionFinds.containsKey(val)) {
                    unionFinds.put(val, new HashMap<Integer, Integer>());
                }
                // relate indices using union find
                joinGroup(unionFinds.get(val), i, ~j);
            }
        }
    
        // organize points by their root index
        SortedMap<Integer, Map<Integer, List<int[]>>> indexedValues = new TreeMap<>();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int val = grid[i][j];
                if (!indexedValues.containsKey(val)) {
                    indexedValues.put(val, new HashMap<Integer, List<int[]>>());
                }
                Map<Integer, List<int[]>> indexMap = indexedValues.get(val);
                int rootIdx = findGroup(unionFinds.get(val), i);
                if (!indexMap.containsKey(rootIdx)) {
                    indexMap.put(rootIdx, new ArrayList<int[]>());
                }
                indexMap.get(rootIdx).add(new int[] { i, j });
            }
        }
    
        int[][] transformedGrid = new int[rows][cols]; // this will hold our transformed ranks
        int[] maxRow = new int[rows]; // highest rank per row
        int[] maxCol = new int[cols]; // highest rank per column
        for (int value : indexedValues.keySet()) {
            for (List<int[]> pointsInGroup : indexedValues.get(value).values()) {
                int rank = 1;
                for (int[] point : pointsInGroup) {
                    rank = Math.max(rank, Math.max(maxRow[point[0]], maxCol[point[1]]) + 1);
                }
                for (int[] point : pointsInGroup) {
                    transformedGrid[point[0]][point[1]] = rank;
                    maxRow[point[0]] = Math.max(maxRow[point[0]], rank);
                    maxCol[point[1]] = Math.max(maxCol[point[1]], rank);
                }
            }
        }
        return transformedGrid;
    }
}

The Java code provided implements a transformation of a matrix based on ranking values within the matrix, employing a Union-Find structure. Here's an in-depth breakdown of the solution:

  • Union-Find Structure Initialization: Initialize Union-Find structures to manage relationships between matrix elements with equal values but potentially different indices.

  • Union Operations: Make union operations on elements of the matrix by relating rows and the inverse of column indices. This helps to form groups based on connectivity within the same matrix values.

  • Mapping Values to Root Indices: After establishing the groups, the next step involves organizing these grouped elements according to their root indices. Each value points to a map, where each map entry contains a list of matrix positions corresponding to that root index.

  • Rank Transformation: Perform the rank transformation by iterating through the stored values in order. For each grouped list of positions:

    1. Calculate the tentative rank for each group by considering the maximum existing ranks in their respective rows and columns.
    2. Assign transformed ranks to positions in the matrix and update the maximum ranks for respective rows and columns accordingly.

Key Implementations:

  • Use of HashMaps and TreeMap to store and sort data efficiently based on matrix values and union roots.
  • Utilization of ArrayList to handle dynamics list operations.

This approach ensures that elements in the matrix are ranked according to both their value and their connectivity, considering the highest rank in neighboring cells (by row and column). This algorithm provides a systematic way to process and transform a matrix with nested map and list structures.

  • Python
python 
class Solution:
    def transformMatrixRank(self, mat: List[List[int]]) -> List[List[int]]:
        rows = len(mat)
        cols = len(mat[0])
    
        # define functions to manage the union-find structure
        def find(parent, idx):
            if idx != parent[idx]:
                parent[idx] = find(parent, parent[idx])
            return parent[idx]
    
        def union(parent, idx1, idx2):
            parent.setdefault(idx1, idx1)
            parent.setdefault(idx2, idx2)
            parent[find(parent, idx1)] = find(parent, idx2)
    
        # Initialize union-finds for each unique value
        valueToUnionFind = {}
        for r in range(rows):
            for c in range(cols):
                val = mat[r][c]
                if val not in valueToUnionFind:
                    valueToUnionFind[val] = {}
                union(valueToUnionFind[val], r, ~c)
    
        # grouping the cells by their root parent
        valueToCells = {}
        for r in range(rows):
            for c in range(cols):
                val = mat[r][c]
                if val not in valueToCells:
                    valueToCells[val] = {}
                root = find(valueToUnionFind[val], r)
                if root not in valueToCells[val]:
                    valueToCells[val][root] = []
                valueToCells[val][root].append((r, c))
    
        res = [[0]*cols for _ in range(rows)]  # Matrix to hold ranks
        maxRow = [0] * rows  # Tracks max rank by rows
        maxCol = [0] * cols  # Tracks max rank by columns
            
        for value in sorted(valueToCells.keys()):
            for groups in valueToCells[value].values():
                curRank = 1
                for r, c in groups:
                    curRank = max(curRank, max(maxRow[r], maxCol[c]) + 1)
                for r, c in groups:
                    res[r][c] = curRank
                    maxRow[r] = max(maxRow[r], curRank)
                    maxCol[c] = max(maxCol[c], curRank)
    
        return res

The provided Python 3 solution outlines the process of transforming the ranks of elements within a matrix. Here's a breakdown of the implementation:

  • Initially, the dimensions of the matrix are determined, and a union-find structure is set up to manage groups of indices that share the same value.

  • Each matrix element is processed to associate its row and column through a union-find mechanism based on its value, enabling clustering of indices having identical data.

  • The find function assists in identifying the root of a node within the union structure. The union function helps merging two nodes to form a single set.

  • Post union-find setup, each value is mapped to its respective cells grouped by union-find roots. The cells associated with a particular value are then stored, grouped by their 'parent' index generated by the union-find algorithm.

  • A new result matrix initialized to zeros is prepared to hold the final ranks. Two arrays, maxRow and maxCol, keep track of the maximum rank found so far in each row and each column, respectively.

  • Processing begins from the smallest to the largest value in the matrix, assigning ranks. Ranks are assigned such that the rank of each element is at least one unit greater than the maximum rank encountered so far in its respective row or column.

  • This ranking mechanism ensures the transitivity of the ranked values as required, iterating over the cell groups and updating the resultant matrix along with the maxRow and maxCol markers accordingly.

The final ranked matrix is returned, representing the new transformed matrix rank based on the criteria described. The solution efficiently manages connected components using union-find and performs ranking in a controlled sequential manner, which adheres to the matrix's constraints.

Comments

No comments yet.