Skip to main content

506. Relative Ranks

easy

Assign medals and ranks to athletes by score. A gentle heap or sort problem that tests how comfortably you can map sorted order back to original indices.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given an integer array score of size n, where score[i] is the score of the ith athlete in a competition. All the scores are guaranteed to be unique. The athletes are placed based on their scores, where the 1st place athlete has the highest score, the 2nd place athlete has the 2nd highest score, and so on. The placement of each athlete determines their rank: 1st place gets 'Gold Medal', 2nd place gets 'Silver Medal', 3rd place gets 'Bronze Medal', and 4th through nth place get their placement number as a string (e.g. '4', '5', ..., 'n'). Return an array answer of size n where answer[i] is the rank of the ith athlete.

Constraints

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

Examples

Example 1

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

Example 2

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

You need to know, for each original index, where its score lands when scores are sorted.

Hint 2

Sort indices by their scores in descending order. The position in that sorted order is the rank minus one.

Hint 3

Heap variant: push (score, index) into a max-heap. Pop n times; the kth pop's index gets rank k.

Hint 4

Convert ranks 1, 2, 3 to medal strings; ranks 4+ become the string of the rank number.

Solution approach

Reveal approach

Two clean options. (1) Sort indices: build an array of indices [0, 1, ..., n-1] and sort by score descending. Walk the sorted indices and write the rank string at answer[sortedIndices[k]]. (2) Max-heap: push (score, index) pairs into a max-heap, then pop n times — the kth pop maps that original index to rank k. Both are O(n log n) time and O(n) space. The heap version is slightly more allocation-heavy but reads naturally in interviews because the 'extract max' operation maps directly to 'next-highest rank'. Edge case: the array is already a permutation, so no ties exist — no tiebreak logic needed.

Complexity

Time
O(n log n)
Space
O(n)

Related patterns

  • heap
  • sorting
  • top-k-elements

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Relative Ranks and Heaps problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →