Relative Ranks — LeetCode 506 Heap and Sort Pattern

Problem Statement#

Given an array score where score[i] is the i-th athlete's score, return their relative ranks. The top three get "Gold Medal", "Silver Medal", "Bronze Medal" respectively; the rest get their rank as a string ("4", "5", ...).

Constraints:

• n == score.length
• 1 <= n <= 10^4
• 0 <= score[i] <= 10^6
• All scores are unique

Input:  score = [5, 4, 3, 2, 1]
Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]

Input:  score = [10, 3, 8, 9, 4]
Output: ["Gold Medal", "5", "Bronze Medal", "Silver Medal", "4"]

Why This Problem Matters#

LeetCode 506 Relative Ranks is a beginner-friendly heap or sort problem that frequently shows up at Amazon, Google, and Microsoft. It tests whether you can sort with index tracking — a skill required by leaderboards, search ranking, and any "return top N with their original positions" problem.

It also gives interviewers a chance to compare two valid approaches: a max-heap solution that streams the top three then drains the rest, or a tuple-sort that pairs scores with indices. Both work; the heap approach generalizes better to streaming.

Keywords: "relative ranks heap", "medal interview", "sort with index", "FAANG ranking problem".

The Core Insight#

We need to know the rank of each score, but we have to write the rank into the result at the original index. So we sort (or heap-pop) by score descending while remembering the original index. Then assign rank labels 1, 2, 3, "4", "5", ...

A max-heap gives this in O(n log n), with an early-exit possibility for the medal positions if you only need top 3. A sort works equally well at this scale.

Visual Dry Run#

Solution (Optimal)#

import heapq
 
class Solution:
    def findRelativeRanks(self, score):
        h = [(-s, i) for i, s in enumerate(score)]
        heapq.heapify(h)
        labels = ["Gold Medal", "Silver Medal", "Bronze Medal"]
        ans = [""] * len(score)
        rank = 1
        while h:
            _, i = heapq.heappop(h)
            ans[i] = labels[rank - 1] if rank <= 3 else str(rank)
            rank += 1
        return ans

class MaxHeap {
    constructor(cmp) { this.h = []; this.cmp = cmp; }
    push(v) { this.h.push(v); this._up(this.h.length - 1); }
    pop() {
        const top = this.h[0], last = this.h.pop();
        if (this.h.length) { this.h[0] = last; this._down(0); }
        return top;
    }
    size() { return this.h.length; }
    _up(i) {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.cmp(this.h[p], this.h[i]) >= 0) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    _down(i) {
        const n = this.h.length;
        while (true) {
            const l = 2 * i + 1, r = 2 * i + 2;
            let s = i;
            if (l < n && this.cmp(this.h[l], this.h[s]) > 0) s = l;
            if (r < n && this.cmp(this.h[r], this.h[s]) > 0) s = r;
            if (s === i) break;
            [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
            i = s;
        }
    }
}
 
var findRelativeRanks = function(score) {
    const h = new MaxHeap((a, b) => a[0] - b[0]);
    for (let i = 0; i < score.length; i++) h.push([score[i], i]);
    const labels = ["Gold Medal", "Silver Medal", "Bronze Medal"];
    const ans = new Array(score.length);
    let rank = 1;
    while (h.size()) {
        const [, i] = h.pop();
        ans[i] = rank <= 3 ? labels[rank - 1] : String(rank);
        rank++;
    }
    return ans;
};

Time: O(n log n) — heapify is O(n), each of n pops is O(log n). Space: O(n) — heap and result.

Common Mistakes#

• Forgetting to track the original index — you cannot recover position from value alone.
• Returning numeric strings starting from 0 or 1 incorrectly (rank starts at 1 = Gold).
• Using a min-heap without negation — gives ascending order.
• Mutating the input array via sort and losing original indices.
• Off-by-one when assigning the "4" string to the 4th-place finisher.

Interview Tips#

• Mention both approaches: heap of pairs and indexed sort. Pick one and justify.
• Note that scores are unique — no tie-breaking required.
• If asked about ties, propose a stable sort by index as a tie-breaker.
• Watch out for the type: result is array of strings, not ints.

Follow-up Questions#

• What if scores can tie? Award same medal and skip ranks (Olympic style) or share rank.
• What if N is huge (10^9)? Stream the heap; you only need top 3 quickly.
• What if you need only the top-3 athletes? Maintain a size-3 min-heap in O(n log 3).
• What if scores arrive online? Two heaps or a balanced BST.

Key Takeaways#

• LeetCode 506 is a heap or sort warmup with index tracking.
• Pair each score with its index before heapifying or sorting.
• Time is O(n log n), space O(n).
• The pattern generalizes to leaderboards and ranked search results.
• Ranks 1, 2, 3 map to Gold, Silver, Bronze; rank N >= 4 maps to str(N).
• Python heapq + tuples handle this in 5 lines.
• JavaScript needs a heap class (or sort) plus index pairing.