Is Restore Finishing Order easy or hard?

Restore Finishing Order is considered an easy problem. The challenge focuses on understanding how to rebuild ordering using ranks and applying a simple custom sort or direct array placement technique.

Restore Finishing Order Python/Java solution

Python implementations typically use sorted() with a key function that returns the stored rank for each participant. Java solutions use Collections.sort or Arrays.sort with a custom comparator referencing the rank map. Both implementations follow the same O(n log n) custom sorting strategy.

How to solve Restore Finishing Order in O(n)?

Create an output array of size n and place each participant directly at index rank - 1. Iterate through the input once and assign participants based on their rank. Since every element is processed exactly once, the algorithm runs in O(n) time with O(n) space.

What is the best approach for Restore Finishing Order?

The most common solution uses custom sorting with a hash map that stores each participant's finishing rank. Sort the participants using a comparator that compares their ranks from the map. This runs in O(n log n) time due to sorting and uses O(n) extra space for the rank map.

Is Restore Finishing Order asked at Google/Amazon/Meta?

Problems involving restoring order from ranking data commonly appear in coding interviews at large tech companies. They test familiarity with arrays, hash tables, and custom sorting—core data structure skills frequently evaluated by companies like Amazon, Google, and Meta.

What data structure is used in Restore Finishing Order?

The primary data structures are arrays and a hash table. The hash table stores the mapping between participants and their finishing rank, enabling constant-time lookups during sorting or placement.

What is the time complexity of Restore Finishing Order?

The typical custom sorting solution runs in O(n log n) time because sorting dominates the runtime. Hash map lookups during comparisons are O(1). If ranks are guaranteed to be in the range 1..n, a direct placement approach can solve it in O(n) time.

Description Hints 2 Solution Video 3:22

3668. Restore Finishing Order

Easy91.1% acceptance2 companies

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 <= 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

Asked at 2 companies

Google Microsoft

Topics

Array Hash Table

Hints open one at a time

Hint 1

Use a hash set for quick friend lookups from friends.

Hint 2

Iterate over order, checking the set to collect your friends in finishing order.

3:22

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def recoverOrder(self, order: List[int], friends: List[int]) -> List[int]:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[3,1,2,5,4]
[1,3,4]

Input

[1,4,5,3,2]
[2,5]

Your code is saved on this device.Solution