Skip to content

3668. Restore Finishing Order

SourceWeekly Contest 465 Q1DifficultyEasyRating1255

Description

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

Solutions

Solution 1: Custom Sorting

Thinking

\(\textit{friends}\) is a subset of \(\textit{order}\) and must be emitted in finish order. \(n\le 100\) allows a rank map and a sort.

Set \(d[x]=i\) from \(\textit{order}\), then sort \(\textit{friends}\) by \(d[x]\).

Comparisons then use finish rank rather than the numeric id.

First, we build a mapping from the order array to record the finishing position of each ID. Then, we sort the friends array based on the finishing order of these IDs in the order array.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the order array.

1
2
3
4
class Solution:
    def recoverOrder(self, order: List[int], friends: List[int]) -> List[int]:
        d = {x: i for i, x in enumerate(order)}
        return sorted(friends, key=lambda x: d[x])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int[] recoverOrder(int[] order, int[] friends) {
        int n = order.length;
        int[] d = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            d[order[i]] = i;
        }
        return Arrays.stream(friends)
            .boxed()
            .sorted((a, b) -> d[a] - d[b])
            .mapToInt(Integer::intValue)
            .toArray();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    vector<int> recoverOrder(vector<int>& order, vector<int>& friends) {
        int n = order.size();
        vector<int> d(n + 1);
        for (int i = 0; i < n; ++i) {
            d[order[i]] = i;
        }
        sort(friends.begin(), friends.end(), [&](int a, int b) {
            return d[a] < d[b];
        });
        return friends;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func recoverOrder(order []int, friends []int) []int {
    n := len(order)
    d := make([]int, n+1)
    for i, x := range order {
        d[x] = i
    }
    sort.Slice(friends, func(i, j int) bool {
        return d[friends[i]] < d[friends[j]]
    })
    return friends
}

1
2
3
4
5
6
7
8
function recoverOrder(order: number[], friends: number[]): number[] {
    const n = order.length;
    const d: number[] = Array(n + 1).fill(0);
    for (let i = 0; i < n; ++i) {
        d[order[i]] = i;
    }
    return friends.sort((a, b) => d[a] - d[b]);
}

Comments