4008. Restore Finishing Order¶

4008. Restore Finishing Order

Easy

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

Solution¶

class Solution {
    static class Pair {
        int node, idx;
        public Pair(int node, int idx) {
            this.node = node;
            this.idx = idx;
        }
        @Override
        public String toString() {
            return "(" + node + " " + idx + ")";
        }
    }
    static class customSort implements Comparator<Pair> {
        @Override
        public int compare(Pair first, Pair second) {
            return Integer.compare(first.idx, second.idx);
        }
    }
    public int[] recoverOrder(int[] order, int[] friends) {
        int n = order.length;
        int pos[] = new int[n + 1];
        for (int i = 0; i < n; i++) 
            pos[order[i]] = i;
        ArrayList<Pair> temp = new ArrayList<>();
        for (int i = 0; i < friends.length; i++)
            temp.add(new Pair(friends[i], pos[friends[i]]));
        Collections.sort(temp, new customSort()); 
        int res[] = new int[friends.length];
        for (int i = 0; i < temp.size(); i++)
            res[i] = temp.get(i).node;
        return res;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Explanation¶

[Add detailed explanation here]