☕ DSA Java Articles

Topics › Heaps › Medium Problems

Replace Elements by Their Rank

Easy TUF ID 898 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given an integer array arr, replace every element by its rank and return the resulting array. Ranks follow three rules:

  1. The smallest value has rank 1, and a larger value has a larger rank.
  2. Equal values have the same rank.
  3. Ranks are as small as possible, so there are no gaps: if the distinct values are d1 < d2 < ... < dm, then di has rank i. (This is “dense” ranking, so two tied values at rank 1 are followed by rank 2, not rank 3.)

Constraints: 0 ≤ n ≤ 10^5, values fit in an int, negatives and duplicates allowed. The input array is left unchanged; a new array is returned.

Example 1

arr = [20, 15, 26, 2, 98, 6]
answer = [4, 3, 5, 1, 6, 2]          // sorted: 2, 6, 15, 20, 26, 98 get ranks 1..6

Example 2

arr = [-5, 0, -5, 7]
answer = [1, 2, 1, 3]                // both -5s share rank 1, and 0 gets rank 2 (no gap)

Approach 1: Brute force, count the distinct smaller values

Intuition. Rule 3 gives a direct formula: the rank of x is one more than the number of distinct values smaller than x. For each element, scan the whole array, put every smaller value into a set (so repeated values count once) and read off the set’s size.

Algorithm.

  1. For each index i:
  2. Create an empty set. For each x in arr, if x < arr[i], add x to the set.
  3. Set rank[i] = set.size() + 1.
static int[] bruteForce(int[] arr) {
    int n = arr.length;
    int[] rank = new int[n];
    for (int i = 0; i < n; i++) {
        Set<Integer> smaller = new HashSet<>();
        for (int x : arr) {
            if (x < arr[i]) smaller.add(x);
        }
        rank[i] = smaller.size() + 1;
    }
    return rank;
}

Complexity. Time O(n^2): n full scans with O(1) average set operations. Space O(n) for the set in the worst case.

Every element repeats the same question, “how many distinct values are below me?”, from scratch. If the values were laid out in sorted order, all the answers could be read off in one sweep.

Approach 2: Sort a copy and map values to ranks

Intuition. Sort a copy of the array. Walking the sorted copy from left to right, the distinct values appear in increasing order, so the first new value gets rank 1, the next new value rank 2, and so on; repeats of a value already seen are skipped. Store the ranks in a hash map from value to rank, then translate the original array through the map. The size of the map at the moment a new value is inserted is exactly the number of distinct values below it, which is precisely the brute-force formula.

Algorithm.

  1. Copy arr and sort the copy.
  2. For each x in the sorted copy: if x is not yet in rankOf, store rankOf[x] = rankOf.size() + 1.
  3. Build the answer with rank[i] = rankOf[arr[i]].
static int[] sortAndMap(int[] arr) {
    int[] sorted = arr.clone();
    Arrays.sort(sorted);
    Map<Integer, Integer> rankOf = new HashMap<>();
    for (int x : sorted) {
        if (!rankOf.containsKey(x)) rankOf.put(x, rankOf.size() + 1);
    }
    int[] rank = new int[arr.length];
    for (int i = 0; i < arr.length; i++) rank[i] = rankOf.get(arr[i]);
    return rank;
}

Complexity. Time O(n log n) for the sort; the two passes are O(n) with average O(1) map operations. Space O(n) for the copy and the map.

Approach 3: Min-heap of value and index pairs

Intuition. This row sits in the heap section because a min-heap is another way to visit the values in increasing order, one at a time. Push a pair {value, index} for every element; popping then yields the elements from smallest to largest, and the stored index tells us where to write the rank. Keep a running rank counter and the previously popped value: when the popped value differs from the previous one, we have reached a new distinct value and the counter goes up by one. Equal values pop consecutively, so they all receive the same counter value. No map is needed, because the index travels with the value.

Algorithm.

  1. Push {arr[i], i} for every i into a min-heap ordered by value.
  2. Set current = 0 and prev to a sentinel that equals no int (a long holding Long.MIN_VALUE).
  3. While the heap is not empty: pop {v, i}. If v != prev, increment current and set prev = v. Write rank[i] = current.
static int[] minHeap(int[] arr) {
    PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> Integer.compare(x[0], y[0]));
    for (int i = 0; i < arr.length; i++) pq.offer(new int[]{arr[i], i});
    int[] rank = new int[arr.length];
    int current = 0;
    long prev = Long.MIN_VALUE;                      // equal to no int, so the first pop opens rank 1
    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        if (top[0] != prev) {
            current++;
            prev = top[0];
        }
        rank[top[1]] = current;
    }
    return rank;
}

Dry run on Example 1, arr = [20, 15, 26, 2, 98, 6]:

popped {value, index} value changed? current rank array
{2, 3} yes 1 [_, _, _, 1, _, _]
{6, 5} yes 2 [_, _, _, 1, _, 2]
{15, 1} yes 3 [_, 3, _, 1, _, 2]
{20, 0} yes 4 [4, 3, _, 1, _, 2]
{26, 2} yes 5 [4, 3, 5, 1, _, 2]
{98, 4} yes 6 [4, 3, 5, 1, 6, 2]

Complexity. Time O(n log n): n pushes and n pops on a heap of size up to n. Space O(n) for the heap of pairs.

Approaches 2 and 3 have the same bound. Sorting is usually faster in practice because Arrays.sort on primitives avoids allocating one small array per element; the heap version is worth knowing because the same “pop in order, carry the index along” pattern solves many problems where elements arrive over time.

Edge cases and pitfalls