0749EasyArrayHash TableStringSorting

Season Leaderboard From Two Parallel Lists

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A club keeps its season results in two lists of the same length. names[i] is the name a competitor entered under and scores[i] is the number of points that same competitor finished on, so position i of one list always refers to the same competitor as position i of the other.

Every score in scores is different from every other, so the ranking never needs a tie-break. Two competitors may still have entered under the same name.

Return the names arranged from the highest score down to the lowest.

Examples

Example 1

Input: names = ["Rhea", "Tomas", "Ines"], scores = [9, 100, 25]
Output: ["Tomas", "Ines", "Rhea"]

Tomas finished on 100, Ines on 25 and Rhea on 9, so that is the order from highest score to lowest.

Example 2

Input: names = ["zeta", "Alpha"], scores = [7, 12]
Output: ["Alpha", "zeta"]

Alpha's 12 beats zeta's 7, so Alpha comes first. The names themselves play no part in the order.

Example 3

Input: names = ["Wu", "Baz", "Kim", "Ana"], scores = [3, 47, 12, 1]
Output: ["Baz", "Kim", "Wu", "Ana"]

The scores from highest to lowest are 47, 12, 3 and 1, which belong to Baz, Kim, Wu and Ana in that order.

Constraints

names.length == scores.length
1 <= names.length <= 10^3
1 <= names[i].length <= 20
1 <= scores[i] <= 10^5
names[i] consists of lowercase and uppercase English letters only.
All the values in scores are different from one another.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def leaderboard(names: list[str], scores: list[int]) -> list[str]:

Java

public String[] leaderboard(String[] names, int[] scores)

The intended approach

Time O(n log n) for n competitors, from the sort.Space O(n) for the index order and the returned list.

The two lists are tied together by position, so sort the positions rather than either list on its own. Order the position indices by the score they point at, largest score first, and then read the names out following that order of indices. Because the scores are all different, the sort key is enough on its own and no secondary key is needed.

Pythonentry point: leaderboard

def leaderboard(names, scores):
    # order the positions by score, largest first, then read the names off in
    # that order. O(n log n) time, O(n) space.
    order = sorted(range(len(names)), key=lambda i: -scores[i])
    return [names[i] for i in order]

The obvious version

Selection sort: scan the positions still unplaced for the largest score, append that competitor's name, remove the position and repeat. Quadratic and uses no sorting routine.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_leaderboard(names, scores):
    """Repeatedly scan what is left for the largest score and take that name out,
    a selection sort over the pairs."""
    left = list(range(len(names)))
    out = []
    while left:
        pick = left[0]
        for i in left:
            if scores[i] > scores[pick]:
                pick = i
        out.append(names[pick])
        left.remove(pick)
    return out

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in