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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Rank Transform of a Matrix

Difficulty: Hard

Problem Description

Given an m x n matrix, return a new matrix 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, calculated based on specific rules regarding the same row and column.

Key Insights

  • The rank starts from 1 and is determined by comparing elements in the same row and column.
  • If two elements are equal, they share the same rank.
  • The rank should be as small as possible while still meeting the comparison criteria.
  • Sorting the elements with their respective positions can help in assigning ranks efficiently.

Space and Time Complexity

Time Complexity: O(m * n * log(m * n)), where m is the number of rows and n is the number of columns (due to sorting). Space Complexity: O(m * n), for storing the ranks in a new matrix.

Solution

To solve this problem, we use the following approach:

  1. Create a list of tuples where each tuple contains an element from the matrix and its corresponding row and column indices.
  2. Sort this list based on the matrix values. This allows us to compare elements easily when assigning ranks.
  3. Initialize a rank matrix of the same size as the input matrix.
  4. Iterate through the sorted list and assign ranks based on the current value and its previous value in the sorted list, ensuring that we respect the rules about ranks in the same row or column.

Data structures used:

  • A list to store the elements along with their indices.
  • A 2D list (matrix) for the ranks.

Code Solutions

def rankTransform(matrix):
    m, n = len(matrix), len(matrix[0])
    elements = [(matrix[i][j], i, j) for i in range(m) for j in range(n)]
    
    # Sort elements based on their values
    elements.sort()
    
    rank_matrix = [[0] * n for _ in range(m)]
    current_rank = 1
    
    for i in range(len(elements)):
        value, row, col = elements[i]
        
        # If it's the same value as the previous one, keep the same rank
        if i > 0 and elements[i - 1][0] == value:
            rank_matrix[row][col] = rank_matrix[elements[i - 1][1]][elements[i - 1][2]]
        else:
            rank_matrix[row][col] = current_rank
        
        current_rank += 1
    
    return rank_matrix
← Back to All Questions