Replace Array Elements with Their Rank: Two Approaches

Replacing each element in an array with its rank means assigning every value a 1-indexed position in ascending sorted order: the smallest element gets rank 1, the second-smallest rank 2, and so on.

The problem has a clean solution using sorting and a hash map. A brute-force alternative exists that avoids the extra space but doubles the time complexity. Both are worth knowing. Placement interviewers sometimes ask for one and then ask you to optimise to the other within the same session.

What the Problem Asks

Given an array of distinct integers, replace each element with its rank in the sorted order of the array. The minimum element always gets rank 1; the maximum element gets rank n (the length of the array).

The canonical example used across most references:

Input:  [10, 8, 15, 12, 6, 20, 1]
Output: [4,  3,  6,  5,  2,  7,  1]

Here is how those output values are derived. Sort the input in ascending order to get the rank sequence:

Sorted position	Value	Rank
1st	1	1
2nd	6	2
3rd	8	3
4th	10	4
5th	12	5
6th	15	6
7th	20	7

Apply those ranks to the original positions:

Index	Original value	Rank assigned	Output
0	10	4	4
1	8	3	3
2	15	6	6
3	12	5	5
4	6	2	2
5	20	7	7
6	1	1	1

Result: [4, 3, 6, 5, 2, 7, 1].

The problem assumes all elements are distinct. For the duplicate-element variant, see LeetCode 1331, which assigns equal ranks to equal values.

HashMap Approach: O(n log n) Time, O(n) Space

The algorithm runs in three steps:

• Step 1: create a sorted copy of the array.
• Step 2: build a rank_map by iterating the sorted copy. The element at index i in the sorted copy gets rank i + 1.
• Step 3: iterate the original array and replace each element with its value from rank_map.

The dominant cost is the sort in Step 1. Steps 2 and 3 are each one linear pass. Total time: O(n log n). The rank_map holds n entries, so auxiliary space is O(n). For a detailed walkthrough of how auxiliary space scales with n, see the space complexity derivation.

GeeksforGeeks covers an equivalent map-based derivation using std::map, which sorts by key automatically and lets you skip the explicit sort step in C++. Both approaches produce the same asymptotic bounds.

Brute Force: O(n²) Time, O(1) Space

The brute-force method derives each element’s rank directly from the definition: rank equals the count of elements smaller than the current element, plus one.

For element 10 in [10, 8, 15, 12, 6, 20, 1]:

• Elements smaller than 10: 8, 6, 1 — count = 3.
• Rank = 3 + 1 = 4.

For element 1:

• No element is smaller — count = 0.
• Rank = 1.

No auxiliary data structure is needed. The trade-off is a nested loop: for each of n elements, the inner loop scans n elements. This gives O(n²) time and O(1) auxiliary space.

When to accept O(n²): for inputs where n is small (up to a few hundred elements) and memory is the hard constraint. In placement coding rounds with typical constraints of n up to 10^5, the HashMap approach is necessary to avoid time-limit errors.

The same O(n) vs. O(n²) trade-off appears in the equilibrium index problem, where computing sums on each iteration is O(n²) and the prefix-sum approach brings it down to O(n).

Code in C++, Python, and Java

HashMap Approach

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> replaceByRank(vector<int> arr) {
    int n = arr.size();
    vector<int> sorted_arr(arr.begin(), arr.end());
    sort(sorted_arr.begin(), sorted_arr.end());

    unordered_map<int, int> rank_map;
    for (int i = 0; i < n; i++) {
        rank_map[sorted_arr[i]] = i + 1;
    }

    for (int i = 0; i < n; i++) {
        arr[i] = rank_map[arr[i]];
    }
    return arr;
}

int main() {
    vector<int> arr = {10, 8, 15, 12, 6, 20, 1};
    vector<int> result = replaceByRank(arr);
    for (int x : result) cout << x << " ";
    // Output: 4 3 6 5 2 7 1
    return 0;
}

Python

def replace_by_rank(arr):
    rank_map = {v: i + 1 for i, v in enumerate(sorted(arr))}
    return [rank_map[x] for x in arr]

arr = [10, 8, 15, 12, 6, 20, 1]
print(replace_by_rank(arr))  # [4, 3, 6, 5, 2, 7, 1]

Java

import java.util.*;

public class ReplaceByRank {
    static int[] replaceByRank(int[] arr) {
        int n = arr.length;
        int[] sorted = arr.clone();
        Arrays.sort(sorted);

        Map<Integer, Integer> rankMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            rankMap.put(sorted[i], i + 1);
        }

        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = rankMap.get(arr[i]);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {10, 8, 15, 12, 6, 20, 1};
        System.out.println(Arrays.toString(replaceByRank(arr)));
        // Output: [4, 3, 6, 5, 2, 7, 1]
    }
}

Brute Force

Python

def replace_by_rank_brute(arr):
    result = []
    for x in arr:
        rank = sum(1 for y in arr if y < x) + 1
        result.append(rank)
    return result

arr = [10, 8, 15, 12, 6, 20, 1]
print(replace_by_rank_brute(arr))  # [4, 3, 6, 5, 2, 7, 1]

Both approaches produce the same output for any array of distinct integers.

Complexity Trade-offs

Approach	Time	Auxiliary space	When to prefer
Sort + HashMap	O(n log n)	O(n)	Default choice; handles n up to 10^6 comfortably
Brute force	O(n²)	O(1)	Only when n is small and memory is the hard constraint

The HashMap space cost is the same class as the map used to find symmetric pairs in an array: O(n) entries, keyed on elements from the input. One pass builds the dictionary; a second pass reads from it.

In placement interviews, stating both approaches in one answer (“O(n²) brute force first, then the O(n log n) HashMap optimisation”) signals that you understand the trade-off and aren’t just pattern-matching to a memorised solution.

---

The sort-then-lookup pattern used above (sorting once to assign stable keys, then doing O(1) lookups) drives ranking and scoring pipelines in production ML systems: top-k retrieval in recommendation engines, percentile normalisation in model evaluation, and score-based filtering in search. TinkerLLM is where you can build those patterns into working LLM projects yourself, starting at ₹299.