Restore Finishing Order - Solution & Explanation

Problem 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.