easy

Relative Ranks

Pop scores out of a max-heap one at a time to hand out gold, silver, bronze and plain placement numbers.

1. Define the problem

Relative Ranks

You are given an array score, where scorei is the result of athlete number i. Every score is different. Return an array where position i holds the placement of athlete i, written as text . The best score gets "Gold Medal", the second best gets "Silver Medal", the third best gets "Bronze Medal", and everyone after that gets their placement number as a string, such as "4". Push every score into a max-heap together with the position it came from, then take the biggest one out again and again. The first value you take out is first place, the second is second place, and so on, so you never have to sort anything yourself.

Constraints

  • 1 ≤ score.length ≤ 104
  • 0 ≤ scorei ≤ 106
  • All values in score are different

Example

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

Explanation From best to worst the scores are 10, 9, 8, 4, 3. Athlete 0 scored 10 and wins gold, athlete 3 scored 9 and takes silver, athlete 2 scored 8 and takes bronze, athlete 4 comes fourth and athlete 1 comes fifth.

2. Know the words first

In plain terms

Heap
A container that always knows its best item, where best means smallest or largest depending on how you set it up. Adding an item or taking the best item out costs about log n steps, and you never have to sort the whole collection.
Backing array
A heap is stored as one plain list. The item at position i keeps its parent at position (i - 1) / 2 rounded down, and its two children at positions 2i + 1 and 2i + 2. That is why every picture below is a row of numbered boxes.
Max-heap
A heap whose best item is the largest one. Looking at the top always shows you the biggest value still inside.
Pop
Removing the top item of a heap. The heap then rearranges itself so the next best item moves to the top.
3. Visualize the solution

The row of boxes is the backing array of the max-heap for score = [10, 3, 8, 9, 4]

The row of boxes is the backing array of the max-heap for score = [10, 3, 8, 9, 4]
Statusinit

The heap starts empty, so every slot of the backing array is unused.

What happens in this step

score = [10, 3, 8, 9, 4]
heap is empty

The heap is told to compare scores biggest first.
Every slot shows — because nothing has been pushed yet.
Step 1 of 6

Steps to visualize

  1. Each box is one slot of the list that stores the heap. Slot 0 is the top of the heap.
  2. A slot showing — is unused right now, because the heap has grown smaller.
  3. Pushing all five scores in builds a max-heap: no slot is ever smaller than its own children.
  4. Then pop five times. Each pop hands back the biggest score still inside, so the values come out in placement order.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

The row of boxes is the backing array of the max-heap for score = [10, 3, 8, 9, 4]
Statusinit

The heap starts empty, so every slot of the backing array is unused.

What happens in this step

score = [10, 3, 8, 9, 4]
heap is empty

The heap is told to compare scores biggest first.
Every slot shows — because nothing has been pushed yet.
Step 1 of 6
5. Solution

Solution

solution.tsTypeScript
function findRelativeRanks(score) {
  const heap = new Heap((a, b) => b[0] - a[0]);

  for (let i = 0; i < score.length; i++) {
    heap.push([score[i], i]);
  }

  const medals = ['Gold Medal', 'Silver Medal', 'Bronze Medal'];
  const answer = new Array(score.length).fill('');

  for (let rank = 1; heap.size() > 0; rank++) {
    const best = heap.pop();
    answer[best[1]] = rank <= 3 ? medals[rank - 1] : String(rank);
  }

  return answer;
}

class Heap {
  constructor(compare) {
    this.items = [];
    this.compare = compare;
  }

  size() {
    return this.items.length;
  }

  peek() {
    return this.items[0];
  }

  push(value) {
    this.items.push(value);
    let child = this.items.length - 1;

    while (child > 0) {
      const parent = (child - 1) >> 1;
      if (this.compare(this.items[child], this.items[parent]) >= 0) break;
      const swap = this.items[child];
      this.items[child] = this.items[parent];
      this.items[parent] = swap;
      child = parent;
    }
  }

  pop() {
    const top = this.items[0];
    const last = this.items.pop();

    if (this.items.length > 0) {
      this.items[0] = last;
      let parent = 0;

      while (true) {
        const left = parent * 2 + 1;
        const right = parent * 2 + 2;
        let best = parent;

        if (left < this.items.length && this.compare(this.items[left], this.items[best]) < 0) best = left;
        if (right < this.items.length && this.compare(this.items[right], this.items[best]) < 0) best = right;
        if (best === parent) break;

        const swap = this.items[parent];
        this.items[parent] = this.items[best];
        this.items[best] = swap;
        parent = best;
      }
    }

    return top;
  }
}
Time
O(n log n)
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
score = [10, 3, 8, 9, 4]["Gold Medal", "5", "Bronze Medal", "Silver Medal", "4"]example from the docstring
score = [5, 4, 3, 2, 1]["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]scores already in best-to-worst order
score = [1]["Gold Medal"]smallest possible input, one athlete
score = [2, 1]["Gold Medal", "Silver Medal"]fewer athletes than medals
score = [7, 9, 2, 4]["Silver Medal", "Gold Medal", "4", "Bronze Medal"]the winner is not at position 0
score = [100, 20, 30, 40, 50, 60]["Gold Medal", "6", "5", "4", "Bronze Medal", "Silver Medal"]more athletes than medals, several plain rank numbers

Keep reading