We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Rank Transform of a Matrix

Number: 1257

Difficulty: Hard

Paid? No

Companies: Citadel, Google

Problem Description

Given an m x n matrix, transform it into a new matrix "answer" such that answer[row][col] is the rank of matrix[row][col]. The rank is defined by the following criteria:

  • 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 ranks should be as small as possible. It is guaranteed that the answer is unique under these rules.

Key Insights

  • Process the matrix cells in increasing order of their values.
  • Group cells with the same value that are in the same row or column using a union–find (disjoint set union) structure.
  • Maintain a rank array for each row and column. When processing a group, determine the new rank as the maximum current rank in that group plus one.
  • Update the rank for each involved row and column and assign the computed rank to the answer matrix.
  • This ensures that the rank assignment maintains all the given constraints.

Space and Time Complexity

Time Complexity: O(m * n * α(m+n)) where α is the inverse Ackermann function (almost constant) – the dominant overhead is sorting all cells. Space Complexity: O(m * n) due to storing rank and union–find structures as well as grouping cells.

Solution

The solution uses a union–find (DSU) data structure to group cells with the same value from the same row or column. We first map every unique value to a list of its cell positions then process these values in sorted order. For each group:

  • Create a DSU for m+n nodes where nodes 0…m-1 represent rows and nodes m…(m+n-1) represent columns.
  • For every cell in the group, union the node corresponding to the row with the node corresponding to the column (offset by m).
  • For each unioned component, determine the maximum rank from the current rows and columns and assign new_rank = max + 1.
  • Update the answer matrix for each cell of the current value and also update the rank for the corresponding row and column. This ensures that when processing subsequent cells, the new rank respects the ordering conditions among rows and columns.

Code Solutions

Below are code implementations with detailed inline comments in Python, JavaScript, C++, and Java.

# Python solution
import collections

# Disjoint set union class
class DSU:
    def __init__(self, size):
        # Initialize parent pointer for each node
        self.parent = list(range(size))
        
    def find(self, x):
        # Path compression technique
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        # Union two sets by connecting their parents
        self.parent[self.find(x)] = self.find(y)

def matrixRankTransform(matrix):
    m, n = len(matrix), len(matrix[0])
    # Group positions by their value
    value_to_positions = collections.defaultdict(list)
    for i in range(m):
        for j in range(n):
            value_to_positions[matrix[i][j]].append((i, j))
    # Initialize rank for m rows and n columns
    rank = [0] * (m + n)
    ans = [[0] * n for _ in range(m)]
    
    # Process each unique value in sorted order
    for value in sorted(value_to_positions):
        dsu = DSU(m + n)
        # For keeping the maximal rank in each union set
        groupMaxRank = {}
        # First pass: union row and column for cells with the current value
        for i, j in value_to_positions[value]:
            dsu.union(i, j + m)
        
        # Second pass: determine the rank for each union group by checking the current rows and columns
        for i, j in value_to_positions[value]:
            parent = dsu.find(i)
            groupMaxRank[parent] = max(groupMaxRank.get(parent, 0), rank[i], rank[j + m])
        
        # Third pass: assign the new rank and update the rank array for rows and columns
        for i, j in value_to_positions[value]:
            parent = dsu.find(i)
            new_rank = groupMaxRank[parent] + 1
            ans[i][j] = new_rank
            rank[i] = new_rank
            rank[j + m] = new_rank
    
    return ans

# Example usage:
# matrix = [[1,2],[3,4]]
# print(matrixRankTransform(matrix))
← Back to All Questions