FastPrepFastPrep
Problem Brief

Drone Delivery Route

FULLTIMENEW GRADOA
See Amazon online assessment and hiring insights

Amazon is expanding a next-generation drone delivery network. The network has m hubs arranged in a circular ring. Hub 1 is adjacent to hub m, and every hub is adjacent to its previous and next hub on the ring.

The array transitionTime has length m. Moving directly between hub i and hub i + 1 takes transitionTime[i - 1] time. Moving directly between hub m and hub 1 takes transitionTime[m - 1] time.

Amazon receives a list of priority delivery requests. The drone must visit the hubs in the order given by requestedHubs. The drone starts at hub 1.

For each requested hub, the drone may move clockwise or counter-clockwise around the ring. Return the minimum total travel time needed to visit all requested hubs in order.

Use 1-based hub indexing for requestedHubs.

1Example 1

Input
transitionTime = [3,2,1], requestedHubs = [1,3,3,2]
Output
3
Explanation

The drone starts at hub 1. Visiting hub 1 costs 0. Moving from hub 1 to hub 3 is shortest through the direct edge between hubs 3 and 1, costing 1. Moving from hub 3 to hub 3 costs 0. Moving from hub 3 to hub 2 costs 2. The total is 3.

2Example 2

Input
transitionTime = [5,1,2,6], requestedHubs = [2,4,1]
Output
14
Explanation

From 1 to 2 costs 5. From 2 to 4, the shortest path is 2 -> 3 -> 4 with cost 1 + 2 = 3. From 4 to 1, the direct edge costs 6. The total is 5 + 3 + 6 = 14.

Constraints

Limits and guarantees your solution can rely on.

  • 1 <= transitionTime.length <= 10^5
  • 1 <= requestedHubs.length <= 10^5
  • 1 <= transitionTime[i] <= 10^9
  • 1 <= requestedHubs[i] <= transitionTime.length
public long getMinimumDroneTime(int[] transitionTime, int[] requestedHubs) {
    // write your code here
}
Input

transitionTime

[3,2,1]

requestedHubs

[1,3,3,2]

Output

3

Sign in to submit your solution.