Watch 10 video solutions for Restore Finishing Order, a easy level problem involving Array, Hash Table. This walkthrough by code kural has 2,077 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array order of length n and an integer array friends.
order contains every integer from 1 to n exactly once, representing the IDs of the participants of a race in their finishing order.friends contains the IDs of your friends in the race sorted in strictly increasing order. Each ID in friends is guaranteed to appear in the order array.Return an array containing your friends' IDs in their finishing order.
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 <= 100order contains every integer from 1 to n exactly once1 <= friends.length <= min(8, n)1 <= friends[i] <= nfriends is strictly increasingProblem Overview: You are given race-related data where each participant is associated with a finishing position. The goal is to reconstruct the final finishing order of all participants. The output should list racers sorted by their finishing rank from first to last.
Approach 1: Custom Sorting with Rank Map (O(n log n) time, O(n) space)
Create a hash map that stores each participant's finishing rank for constant-time lookup. Then apply a custom sort on the list of participants where the comparator checks the stored rank in the map. During sorting, each comparison reads two ranks and orders the racers accordingly. Sorting dominates the runtime, resulting in O(n log n) time while the rank map requires O(n) extra space.
This approach works well when the input participants are not already ordered by rank. The key insight is separating data storage (hash map for ranks) from ordering logic (custom comparator). Languages like Python use sorted(..., key=...), while Java or C++ rely on custom comparator functions. The hash table ensures each rank lookup is constant time during comparisons.
Approach 2: Direct Placement Using Rank Index (O(n) time, O(n) space)
If finishing ranks are guaranteed to be unique and range from 1..n, you can skip sorting entirely. Create a result array of size n and place each participant directly at index rank - 1. Iterate through the input once, insert the participant into the correct position, and return the array. This turns the problem into a simple indexing operation.
The runtime becomes O(n) since each participant is processed exactly once, and the space cost is the output array itself. This technique is common when working with arrays where positions directly represent ranks.
Recommended for interviews: The custom sorting approach is the most natural solution because it works for any rank representation and clearly demonstrates how to combine hash table lookups with a comparator. The direct placement optimization shows deeper understanding when ranks form a contiguous range and you recognize that sorting can be avoided.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Custom Sorting with Rank Map | O(n log n) | O(n) | General case where ranks are stored separately and ordering must be reconstructed |
| Direct Placement Using Rank Index | O(n) | O(n) | When ranks are unique and fall within the range 1..n |