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

Difficulty: Easy

Problem Description

Given an array of integers arr, replace each element with its rank. The rank represents how large the element is, following specific rules: rank starts from 1, larger elements have larger ranks, equal elements share the same rank, and ranks should be as small as possible.

Key Insights

  • The problem requires ranking the elements of an array based on their values.
  • Equal elements must have the same rank.
  • Sorting the unique elements helps in determining the ranks efficiently.
  • A mapping of the elements to their ranks allows for easy transformation of the original array.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the array. Space Complexity: O(n) - for storing the ranks and unique elements.

Solution

To solve this problem, we can use the following approach:

  1. Create a sorted list of the unique elements from the input array.
  2. Use a hash map (or dictionary) to map each unique element to its rank (index + 1).
  3. Iterate through the original array and replace each element with its corresponding rank using the hash map.

This approach ensures that we efficiently determine the rank for each element while handling duplicates correctly.

Code Solutions

def arrayRankTransform(arr):
    # Step 1: Create a sorted list of unique elements
    unique_sorted = sorted(set(arr))
    
    # Step 2: Create a mapping of each unique element to its rank
    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]
← Back to All Questions