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 an Array

Number: 1256

Difficulty: Easy

Paid? No

Companies: Meta, Google, Amazon, Bloomberg

Problem Description

Given an array of integers, replace each element with its rank. The rank of an element is defined as its position in the sorted order of the unique elements of the array (starting from 1). If two elements are equal, they share the same rank.

Key Insights

  • Sorting the unique elements of the array helps to assign the smallest rank to the smallest element.
  • A hash table (dictionary/map) is used to map each unique element to its corresponding rank.
  • Iterating over the array and replacing elements using the hash table results in the final rank-transformed array.
  • Handling duplicate elements properly ensures that equal elements receive the same rank.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the unique elements. Space Complexity: O(n) for the hash table and the output array.

Solution

We can solve the problem using the following approach:

  1. Extract the unique elements from the array.
  2. Sort these unique elements in ascending order.
  3. Create a mapping (hash table) where each unique element is assigned its rank (starting from 1).
  4. Iterate through the original array and replace each element with its corresponding rank from the mapping. This approach efficiently handles duplicates and ensures that the rank is as small as possible for each element.

Code Solutions

# Python solution for Rank Transform of an Array

def rank_transform(arr):
    # Step 1: Create a sorted list of unique elements
    unique_sorted = sorted(set(arr))
    
    # Step 2: Map each unique element to its rank (starting from 1)
    rank_map = {num: rank + 1 for rank, num in enumerate(unique_sorted)}
    
    # Step 3: Replace each element in the original array with its rank
    return [rank_map[num] for num in arr]

# Example usage:
arr = [40, 10, 20, 30]
print(rank_transform(arr))  # Output: [4, 1, 2, 3]
← Back to All Questions