LeetCode 3668 - Restore Finishing Order

This problem gives us two arrays: - order, which represents the finishing order of all participants in a race. - friends, which contains the IDs of our friends. The array order is a permutation of the integers from 1 to n, meaning every participant appears exactly once.

leetcodeeasyarrayhash-table

LeetCode Problem 3668

Difficulty: 🟢 Easy
Topics: Array, Hash Table

Solution

LeetCode 3668 - Restore Finishing Order

Problem Understanding

This problem gives us two arrays:

  • order, which represents the finishing order of all participants in a race.
  • friends, which contains the IDs of our friends.

The array order is a permutation of the integers from 1 to n, meaning every participant appears exactly once. The position of a participant in order tells us where they finished in the race. Earlier positions correspond to better finishing places.

The array friends contains a subset of participant IDs. These IDs are sorted in strictly increasing order, but that sorting has nothing to do with their race results. Our goal is to determine how these friends actually finished relative to one another.

In other words, we need to extract from order only those participants who appear in friends, while preserving the original race order.

For example, if:

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

the race finished as:

3 → 1 → 2 → 5 → 4

Among the friends {1,3,4}, the participants appear in the race order:

3 → 1 → 4

so the answer is:

[3,1,4]

The constraints are very small:

  • n ≤ 100
  • friends.length ≤ 8

This tells us that even simple solutions will run extremely fast. Nevertheless, we should still identify the most direct and efficient approach.

An important guarantee is that every friend ID appears in order. Therefore, we never need to handle missing values.

Some potential edge cases include:

  • Only one friend exists.
  • Every participant is a friend.
  • Friends finish consecutively.
  • Friends finish far apart in the race order.
  • The friends array is sorted numerically but their finishing order is completely different.

Because all IDs are unique and guaranteed to exist in order, we do not need to worry about duplicates or invalid inputs.

Approaches

Brute Force

A straightforward solution is to process each friend separately.

For every friend ID, we can scan through order to find its finishing position. After finding all positions, we can sort the friends according to those positions and return the resulting order.

This works because the finishing position completely determines the relative order of friends.

However, for each friend we may scan the entire order array. If there are f friends and n participants, this requires O(f × n) time.

Although the constraints are tiny and this approach is acceptable here, it performs unnecessary repeated scans.

Optimal Approach

The key observation is that we already have the finishing order in order.

Instead of finding each friend's position, we can simply walk through order once and keep only the participants who are friends.

To make friend membership checks efficient, we store all friend IDs in a hash set.

As we iterate through order:

  • If the current participant is a friend, append them to the answer.
  • Otherwise, skip them.

Since order is already arranged in finishing order, the resulting list automatically has the correct ordering.

This eliminates the need to search for positions or perform any sorting.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n × f) O(f) Find each friend's position separately, then sort by position
Optimal O(n + f) O(f) Use a hash set and filter the race order directly

Where:

  • n = len(order)
  • f = len(friends)

Algorithm Walkthrough

  1. Create a hash set containing all IDs from friends.

This allows constant-time membership checks when examining race participants. 2. Create an empty result array.

This will store friends in their actual finishing order. 3. Iterate through each participant ID in order.

Since order already represents the race finishing sequence, processing it from left to right preserves that order. 4. For each participant, check whether it exists in the friends set.

If it does, append it to the result array. 5. Continue until all participants have been processed. 6. Return the result array.

Why it works

The array order lists participants exactly in finishing order. During the scan, every friend is encountered at precisely the position corresponding to their finish. By appending only friend IDs while preserving the traversal order, we produce exactly the subsequence of order consisting of friends. Therefore, the returned array matches the friends' finishing order.

Python Solution

from typing import List

class Solution:
    def recoverOrder(self, order: List[int], friends: List[int]) -> List[int]:
        friend_set = set(friends)
        result = []

        for participant in order:
            if participant in friend_set:
                result.append(participant)

        return result

The implementation begins by converting friends into a hash set. This allows membership checks in constant average time.

Next, an empty list called result is created. We then scan the order array from left to right. Whenever the current participant belongs to the friend set, we append that participant to result.

Because we process participants in race order, the resulting list automatically preserves the correct finishing sequence. After the scan completes, the result is returned.

Go Solution

func recoverOrder(order []int, friends []int) []int {
	friendSet := make(map[int]bool)

	for _, friend := range friends {
		friendSet[friend] = true
	}

	result := make([]int, 0)

	for _, participant := range order {
		if friendSet[participant] {
			result = append(result, participant)
		}
	}

	return result
}

The Go implementation follows the same logic as the Python version. A map is used as a hash set for constant-time membership checks. We then scan the order slice once and append matching participants to the result slice.

There are no special concerns regarding integer overflow because all values are at most 100. The function naturally returns an empty slice only if no friends are found, though the problem guarantees at least one friend exists.

Worked Examples

Example 1

Input

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

Create the set:

friend_set = {1,3,4}
Participant In friend_set? Result
3 Yes [3]
1 Yes [3,1]
2 No [3,1]
5 No [3,1]
4 Yes [3,1,4]

Final answer:

[3,1,4]

Example 2

Input

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

Create the set:

friend_set = {2,5}
Participant In friend_set? Result
1 No []
4 No []
5 Yes [5]
3 No [5]
2 Yes [5,2]

Final answer:

[5,2]

Complexity Analysis

Measure Complexity Explanation
Time O(n + f) Building the set takes O(f), scanning order takes O(n)
Space O(f) The hash set stores all friend IDs

The algorithm performs a single pass over the friends array to build the hash set and a single pass over the order array to construct the answer. No sorting or nested iteration is required. The only auxiliary memory used is the hash set containing the friend IDs.

Test Cases

from typing import List

class Solution:
    def recoverOrder(self, order: List[int], friends: List[int]) -> List[int]:
        friend_set = set(friends)
        return [x for x in order if x in friend_set]

s = Solution()

assert s.recoverOrder([3,1,2,5,4], [1,3,4]) == [3,1,4]  # Example 1
assert s.recoverOrder([1,4,5,3,2], [2,5]) == [5,2]      # Example 2

assert s.recoverOrder([1], [1]) == [1]                  # Single participant
assert s.recoverOrder([1,2,3], [1,2,3]) == [1,2,3]      # Everyone is a friend
assert s.recoverOrder([3,2,1], [1]) == [1]              # Single friend
assert s.recoverOrder([5,4,3,2,1], [1,3,5]) == [5,3,1]  # Reverse finish order
assert s.recoverOrder([2,1,4,3], [1,3]) == [1,3]        # Friends separated by others
assert s.recoverOrder([4,1,3,2], [2,4]) == [4,2]        # Different numerical and finish order
assert s.recoverOrder([2,3,1,5,4], [1,4]) == [1,4]      # Friends near end
assert s.recoverOrder([6,1,5,2,4,3], [1,2,3]) == [1,2,3]  # Multiple matches

Test Summary

Test Why
[3,1,2,5,4], [1,3,4] Provided example
[1,4,5,3,2], [2,5] Provided example
[1], [1] Smallest valid input
[1,2,3], [1,2,3] Every participant is a friend
[3,2,1], [1] Single friend
[5,4,3,2,1], [1,3,5] Friends appear in reverse numerical order
[2,1,4,3], [1,3] Friends separated by non-friends
[4,1,3,2], [2,4] Finishing order differs from numeric order
[2,3,1,5,4], [1,4] Friends appear late in the race
[6,1,5,2,4,3], [1,2,3] Multiple friend matches throughout the array

Edge Cases

Only One Friend

If friends contains exactly one ID, the answer must contain that same ID. A buggy implementation might overcomplicate the ordering logic or accidentally exclude the participant. The hash-set filtering approach naturally includes the participant exactly once when encountered in order.

Every Participant Is a Friend

When friends contains all participants, the correct answer is simply the entire order array. Since every membership test succeeds, the algorithm appends every participant and reproduces the original finishing order exactly.

Friends Are Sorted Numerically but Finish Differently

The friends array is guaranteed to be sorted in increasing numeric order, but that order has no relation to race results. For example:

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

The correct output is:

[5,3,1]

A common mistake is to return friends unchanged or sort friends numerically after processing. The implementation avoids this issue by relying solely on the ordering provided by order.

Friends Appear Far Apart in the Race

Friends may be separated by many non-friends in the order array. The algorithm correctly skips all non-friends and retains only the desired participants. Because it scans the entire race order once, the distance between friends does not affect correctness.