Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Rank Transform of an Array

EASYProblemSolveExternal Links

Description

Given an array of integers arr, replace each element with its rank.

The rank of an element represents its relative size compared to all other elements in the array. The ranking rules are:

  1. Rank starts from 1. The smallest element receives rank 1.
  2. Larger elements get larger ranks. If element A is greater than element B, then A's rank must be strictly greater than B's rank.
  3. Equal elements share the same rank. If two or more elements have the same value, they must all receive the same rank.
  4. Ranks must be as small as possible. Ranks should use consecutive integers starting from 1 with no gaps. For example, if the unique sorted values are [5, 10, 20], ranks should be [1, 2, 3] — not [1, 2, 4].

Return the transformed array where each original element is replaced by its corresponding rank.

Examples

Example 1

Input: arr = [40, 10, 20, 30]

Output: [4, 1, 2, 3]

Explanation: When we sort the unique values in ascending order, we get [10, 20, 30, 40]. The value 10 is the smallest, so it receives rank 1. The value 20 is the second smallest (rank 2), 30 is the third smallest (rank 3), and 40 is the largest (rank 4). Replacing each element in the original array with its rank produces [4, 1, 2, 3].

Example 2

Input: arr = [100, 100, 100]

Output: [1, 1, 1]

Explanation: All three elements have the same value 100. Since equal elements must share the same rank and ranks start from 1, every element gets rank 1. There are no other distinct values, so rank 1 is the only rank assigned.

Example 3

Input: arr = [37, 12, 28, 9, 100, 56, 80, 5, 12]

Output: [5, 3, 4, 2, 8, 6, 7, 1, 3]

Explanation: The unique values sorted in ascending order are [5, 9, 12, 28, 37, 56, 80, 100], giving 8 distinct ranks. Notice that the value 12 appears twice (at indices 1 and 8), and both occurrences receive the same rank of 3. The smallest value 5 gets rank 1, and the largest value 100 gets rank 8.

Constraints

  • 0 ≤ arr.length ≤ 10^5
  • -10^9 ≤ arr[i] ≤ 10^9

Editorial

Brute Force

Intuition

The most straightforward way to find the rank of any element is to answer a simple question: how many distinct values in the array are strictly smaller than this element? The rank is simply that count plus one.

Imagine you are standing in a line of people sorted by height. Your rank is determined by how many people with different heights are shorter than you, plus one (to account for yourself). If two people have the exact same height, they share the same rank because the same number of distinct shorter heights exist below both of them.

For each element in the array, we scan through the entire array, collect all distinct values that are smaller, and compute the rank from that count. This approach checks every possible pair of elements.

Step-by-Step Explanation

Let's trace through with arr = [40, 10, 20, 30]:

Step 1: Start with element arr[0] = 40. We need to scan the entire array and count how many distinct values are strictly less than 40.

Step 2: Compare with arr[1] = 10. Is 10 < 40? Yes. We found 1 distinct value smaller than 40.

Step 3: Compare with arr[2] = 20. Is 20 < 40? Yes. Now we have 2 distinct smaller values: {10, 20}.

Step 4: Compare with arr[3] = 30. Is 30 < 40? Yes. We now have 3 distinct smaller values: {10, 20, 30}. Scan complete for element 40. Rank = 3 + 1 = 4.

Step 5: Move to arr[1] = 10. Scan the entire array: arr[0] = 40 — is 40 < 10? No. arr[2] = 20 — is 20 < 10? No. arr[3] = 30 — is 30 < 10? No.

Step 6: Zero distinct values are smaller than 10. Rank = 0 + 1 = 1. The value 10 is the smallest element in the array.

Step 7: For arr[2] = 20: scanning the array, only the value 10 is smaller. 1 distinct smaller value → rank = 2.

Step 8: For arr[3] = 30: values 10 and 20 are smaller. 2 distinct smaller values → rank = 3.

Result: The transformed array is [4, 1, 2, 3].

Brute Force — Counting Distinct Smaller Values — Watch how we scan the entire array for each element, collecting distinct values that are strictly smaller, then compute the rank as count + 1.

Algorithm

  1. Create a result array of the same length as the input.
  2. For each element arr[i] (from index 0 to n-1):
    a. Initialize an empty set to track distinct smaller values.
    b. Scan through every element arr[j] in the array.
    c. If arr[j] < arr[i], add arr[j] to the set.
    d. After scanning, set result[i] = size of the set + 1.
  3. Return the result array.

Code

#include <vector>
#include <set>
using namespace std;

class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        int n = arr.size();
        vector<int> result(n);
        
        for (int i = 0; i < n; i++) {
            set<int> smaller;
            for (int j = 0; j < n; j++) {
                if (arr[j] < arr[i]) {
                    smaller.insert(arr[j]);
                }
            }
            result[i] = smaller.size() + 1;
        }
        
        return result;
    }
};
class Solution:
    def arrayRankTransform(self, arr: list[int]) -> list[int]:
        n = len(arr)
        result = [0] * n
        
        for i in range(n):
            smaller = set()
            for j in range(n):
                if arr[j] < arr[i]:
                    smaller.add(arr[j])
            result[i] = len(smaller) + 1
        
        return result
import java.util.*;

class Solution {
    public int[] arrayRankTransform(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        
        for (int i = 0; i < n; i++) {
            Set<Integer> smaller = new HashSet<>();
            for (int j = 0; j < n; j++) {
                if (arr[j] < arr[i]) {
                    smaller.add(arr[j]);
                }
            }
            result[i] = smaller.size() + 1;
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n²)

For each of the n elements, we scan the entire array of n elements to find all values that are strictly smaller. The outer loop runs n times and the inner loop runs n times for each iteration, giving n × n = n² comparisons in total. The set operations add a logarithmic factor, but the quadratic scan dominates the runtime.

Space Complexity: O(n)

For each element, we maintain a set that can hold at most n distinct values. This set is rebuilt for every element, so at any point we use at most O(n) extra space. The result array also requires O(n) space.

Why This Approach Is Not Efficient

The brute force approach performs O(n²) work because for every single element, it scans the entire array. With n up to 10^5, this means up to 10^10 operations — far exceeding what can be computed within typical time limits (roughly 10^8 operations per second).

The core inefficiency is repeated work: every element independently discovers the relative ordering of ALL values. But the relative ordering of values is a global property of the array — it only needs to be computed once.

Key insight: If we sort all unique values just once, we immediately know each value's rank — its position in the sorted order. Instead of re-discovering the ordering for every element (O(n) per element), we can precompute a lookup table and answer rank queries in O(1) per element. Sorting costs O(n log n) once, and then n lookups cost O(n) total, reducing the overall time from O(n²) to O(n log n).

Bar chart comparing O(n²) brute force with 10 billion operations vs O(n log n) sorting approach with 1.7 million operations for n = 100,000
Bar chart comparing O(n²) brute force with 10 billion operations vs O(n log n) sorting approach with 1.7 million operations for n = 100,000

Optimal Approach - Sorting with Hash Map

Intuition

Instead of rediscovering the relative ordering for every element, we can compute it once and reuse it. The strategy has two phases:

Phase 1 — Build the rank map: Extract all unique values from the array and sort them. The position of each value in this sorted list IS its rank (position 0 → rank 1, position 1 → rank 2, and so on). Store these value-to-rank mappings in a hash map for instant lookups.

Phase 2 — Transform the array: Walk through the original array. For each element, look up its rank in the hash map (an O(1) operation) and write it to the result.

Think of it like creating a phone book. Instead of asking every person in a crowd "who is shorter than me?" over and over, you line everyone up by height once, write down each person's position, and then hand out position cards. The lineup (sorting) takes some effort, but once it is done, answering "what is my rank?" is instant for anyone.

Duplicate values are handled automatically: when we extract unique values with a set, duplicates collapse into a single entry. Both occurrences of the same value map to the same rank.

Step-by-Step Explanation

Let's trace through with arr = [40, 10, 20, 30]:

Step 1: Extract unique values from the array: {10, 20, 30, 40}. Sort them in ascending order: [10, 20, 30, 40]. This sorted list defines the rank mapping.

Step 2: Assign rank 1 to the smallest unique value: 10 → rank 1. Store {10: 1} in the rank map.

Step 3: Assign rank 2 to the next unique value: 20 → rank 2. Store {20: 2}.

Step 4: Assign rank 3 to 30. Store {30: 3}.

Step 5: Assign rank 4 to 40 (the largest). Store {40: 4}. The complete rank map is {10: 1, 20: 2, 30: 3, 40: 4}.

Step 6: Now transform the original array. Look up arr[0] = 40 in the rank map → rank 4. Result so far: [4].

Step 7: Look up arr[1] = 10 → rank 1. Result: [4, 1].

Step 8: Look up arr[2] = 20 → rank 2. Result: [4, 1, 2].

Step 9: Look up arr[3] = 30 → rank 3. Result: [4, 1, 2, 3].

Result: The transformed array is [4, 1, 2, 3]. We sorted once (4 elements) and performed 4 instant lookups — far fewer operations than the brute force.

Sorting + Hash Map — Build Once, Look Up Instantly — Watch how we build a rank map from sorted unique values, then transform every element in the original array with O(1) hash map lookups.

Algorithm

  1. Extract all unique values from the array (using a set).
  2. Sort the unique values in ascending order.
  3. Build a hash map: for each unique value at position i in the sorted list, store {value → i + 1} as its rank.
  4. Create a result array of the same length as the input.
  5. For each element arr[i] in the original array, set result[i] = hash_map[arr[i]].
  6. Return the result array.

Code

#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        // Step 1: Extract unique values and sort them
        vector<int> sorted_arr(arr.begin(), arr.end());
        sort(sorted_arr.begin(), sorted_arr.end());
        sorted_arr.erase(
            unique(sorted_arr.begin(), sorted_arr.end()),
            sorted_arr.end()
        );
        
        // Step 2: Build rank map (value -> rank)
        unordered_map<int, int> rankMap;
        for (int i = 0; i < sorted_arr.size(); i++) {
            rankMap[sorted_arr[i]] = i + 1;
        }
        
        // Step 3: Transform original array using rank map
        vector<int> result(arr.size());
        for (int i = 0; i < arr.size(); i++) {
            result[i] = rankMap[arr[i]];
        }
        return result;
    }
};
class Solution:
    def arrayRankTransform(self, arr: list[int]) -> list[int]:
        # Step 1: Extract unique values and sort them
        sorted_unique = sorted(set(arr))
        
        # Step 2: Build rank map (value -> rank)
        rank_map = {val: rank + 1 for rank, val in enumerate(sorted_unique)}
        
        # Step 3: Transform original array using rank map
        return [rank_map[x] for x in arr]
import java.util.*;

class Solution {
    public int[] arrayRankTransform(int[] arr) {
        // Step 1: Extract unique values and sort them
        TreeSet<Integer> uniqueSet = new TreeSet<>();
        for (int num : arr) {
            uniqueSet.add(num);
        }
        
        // Step 2: Build rank map (value -> rank)
        Map<Integer, Integer> rankMap = new HashMap<>();
        int rank = 1;
        for (int num : uniqueSet) {
            rankMap.put(num, rank++);
        }
        
        // Step 3: Transform original array using rank map
        int[] result = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            result[i] = rankMap.get(arr[i]);
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

The algorithm has three phases:

  • Creating the set of unique values: O(n) to iterate through the array.
  • Sorting the unique values: O(m log m) where m is the number of unique elements. In the worst case, all elements are unique and m = n, making this O(n log n).
  • Building the rank map: O(m) to iterate through sorted unique values.
  • Transforming the original array: O(n) with O(1) hash map lookups per element.

The sorting step dominates, giving an overall time complexity of O(n log n).

Space Complexity: O(n)

We store:

  • A set/sorted list of unique values: O(m) where m ≤ n.
  • A hash map with m entries: O(m).
  • The result array: O(n).

In the worst case (all elements are unique), m = n, so total space is O(n).