Editor

Where Would You Have Placed?

#632 · Sorting and searching · Advanced · Fast enough · 110 XP · about 18 min

A city marathon keeps every finishing time from last year's race, in seconds, in no particular order. This year's runners want to know where they would have finished in that race. A runner's place is 1 plus the number of last year's runners who were strictly faster, so runners with equal times share a place.

Write places(last_year, this_year) that returns a list with the place of each time in this_year, in the same order.

Examples

places([300, 200, 400], [250, 100, 400, 500])  # returns [2, 1, 3, 4]
places([10, 10, 10], [10, 11])                 # returns [1, 4]
places([5], [])                                # returns []

In the first example only the 200-second runner beat 250, so 250 would have placed 2nd. A time of 400 ties with last year's slowest runner and shares 3rd place.

Constraints

  • 1 <= len(last_year) <= 200,000
  • 0 <= len(this_year) <= 200,000
  • Times are whole numbers from 1 to 1,000,000.

Time limit

Each test must finish within 10 seconds, and the hidden tests have 200,000 runners in each race.

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.