Restore Finishing Order

Difficulty: Easy | Acceptance: 91.20% | Paid: No Topics: Array, Hash Table

There is a race with n runners numbered from 0 to n - 1. You are given an array finishPosition of size n, where finishPosition[i] represents the number of runners who finished before the i-th runner. The finishing positions are 0-indexed (0 means no one finished before, i.e., first place).

Return an array result of size n where result[j] represents the runner who finished in position j (i.e., the runner who has exactly j runners before them).

• Examples
• Constraints
• Direct Array Construction
• Sorting Approach
• Hash Map Approach

Examples

Example 1

Input:

order = [3,1,2,5,4], friends = [1,3,4]

Output:

[3,1,4]

Explanation: The finishing order is [3, 1, 2, 5, 4]. Therefore, the finishing order of your friends is [3, 1, 4].

Example 2

Input:

order = [1,4,5,3,2], friends = [2,5]

Output:

[5,2]

Explanation: The finishing order is [1, 4, 5, 3, 2]. Therefore, the finishing order of your friends is [5, 2].

Constraints

- 1 <= n == order.length <= 100
- order contains every integer from 1 to n exactly once
- 1 <= friends.length <= min(8, n)
- 1 <= friends[i] <= n
- friends is strictly increasing

Direct Array Construction

Intuition Since finishPosition[i] tells us the position where runner i should be placed, we can directly place each runner at their corresponding position in a new result array.

Steps

• Create a result array of size n
• For each runner, place them at index finishPosition[runner] in the result array
• Return the result array

from typing import List

class Solution:
    def restoreFinishingOrder(self, finishPosition: List[int]) -> List[int]:
        n = len(finishPosition)
        result = [0] * n
        for runner in range(n):
            result[finishPosition[runner]] = runner
        return result

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Optimal solution with single pass through the array

Sorting Approach

Intuition Create pairs of (position, runner) and sort by position to get the finishing order.

Steps

• Create pairs of (finishPosition[i], i) for each runner i
• Sort the pairs by the first element (position)
• Extract the runner values from the sorted pairs

from typing import List

class Solution:
    def restoreFinishingOrder(self, finishPosition: List[int]) -> List[int]:
        pairs = [(finishPosition[i], i) for i in range(len(finishPosition))]
        pairs.sort()
        return [runner for _, runner in pairs]

Complexity

• Time: O(n log n)
• Space: O(n)
• Notes: Sorting adds overhead compared to direct array construction

Hash Map Approach

Intuition Use a hash map to store the mapping from position to runner, then build the result array by looking up each position.

Steps

• Create a hash map mapping position to runner
• For each position from 0 to n-1, look up the corresponding runner
• Build and return the result array

from typing import List

class Solution:
    def restoreFinishingOrder(self, finishPosition: List[int]) -> List[int]:
        n = len(finishPosition)
        position_to_runner = {}
        for runner in range(n):
            position_to_runner[finishPosition[runner]] = runner
        result = [position_to_runner[pos] for pos in range(n)]
        return result

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Hash map overhead makes it slightly less efficient than direct array construction