Minimum Drone Delivery Time on a Ring of Hubs
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A fleet operator runs a single delivery drone over a set of `m` hubs arranged in a circle (a ring). The hubs are numbered `1` through `m` in clockwise order (1-indexed), and hub `m` is adjacent to hub `1`, closing the loop. Moving between two **adjacent** hubs — in either direction — takes exactly one unit of time.
The drone always starts at hub `1`. It must then visit a list of hubs `requestedHubs` **in the given order**: first it flies from hub `1` to `requestedHubs[0]`, then from `requestedHubs[0]` to `requestedHubs[1]`, and so on, until the last requested hub has been visited.
For each individual leg of the trip (from the drone's current hub to the next requested hub), the drone may choose to fly **clockwise** or **counterclockwise**, and it always takes the cheaper of the two directions for that leg — i.e. the minimum number of adjacency steps around the ring between the two hubs.
Return the **total minimum delivery time**: the sum, over all legs, of the shortest distance around the ring between consecutive hubs in the route (starting from hub `1`).
### Notes
- A "leg" is a move from one hub to the next hub in the route. The route is `[1, requestedHubs[0], requestedHubs[1], ..., requestedHubs[n-1]]`.
- The shortest distance between two hubs `a` and `b` on a ring of `m` hubs is `min(d, m - d)` where `d = |a - b|`.
- If a requested hub equals the drone's current hub, that leg costs `0`.
### Constraints
- `2 <= m <= 10^9` (the ring can have as few as 2 hubs — handle the `m = 2` ring carefully, where clockwise and counterclockwise distances between the two hubs are equal).
- `1 <= requestedHubs.length <= 10^5`.
- Each entry of `requestedHubs` is an integer in `[1, m]`.
### Input / Output
- **Input:** an integer `m` and an integer array `requestedHubs`.
- **Output:** a single integer — the total minimum delivery time.
### Examples
**Example 1**
```
m = 6
requestedHubs = [4, 2]
Output: 5
```
Explanation: Start at hub 1. Leg 1: hub 1 to hub 4 — clockwise distance is 3, counterclockwise is 3, so 3. Leg 2: hub 4 to hub 2 — distance |4-2| = 2, and 6-2 = 4, so min is 2. Total = 3 + 2 = 5.
**Example 2**
```
m = 2
requestedHubs = [2, 1, 2]
Output: 3
```
Explanation: Ring of 2 hubs; the two hubs are adjacent, and the distance between hub 1 and hub 2 is 1 in either direction (`min(1, 2 - 1) = 1`). Legs: 1 to 2 (1), 2 to 1 (1), 1 to 2 (1). Total = 3.
**Example 3**
```
m = 5
requestedHubs = [3]
Output: 2
```
Explanation: Hub 1 to hub 3 — clockwise distance 2, counterclockwise 3, min is 2.
Quick Answer: This question tests a candidate's grasp of circular graph traversal and greedy distance minimization on ring-structured topologies. It evaluates algorithm design for sequential shortest-path accumulation, commonly assessed in coding interviews to gauge proficiency with modular arithmetic and edge-case handling in constrained traversal problems.
A fleet operator runs a single delivery drone over a set of `m` hubs arranged in a circle (a ring). The hubs are numbered `1` through `m` in clockwise order (1-indexed), and hub `m` is adjacent to hub `1`, closing the loop. Moving between two **adjacent** hubs — in either direction — takes exactly one unit of time.
The drone always starts at hub `1`. It must then visit a list of hubs `requestedHubs` **in the given order**: first it flies from hub `1` to `requestedHubs[0]`, then from `requestedHubs[0]` to `requestedHubs[1]`, and so on, until the last requested hub has been visited.
For each individual leg of the trip (from the drone's current hub to the next requested hub), the drone may choose to fly **clockwise** or **counterclockwise**, and it always takes the cheaper of the two directions for that leg — i.e. the minimum number of adjacency steps around the ring between the two hubs.
Return the **total minimum delivery time**: the sum, over all legs, of the shortest distance around the ring between consecutive hubs in the route (starting from hub `1`).
### Notes
- A "leg" is a move from one hub to the next hub in the route. The route is `[1, requestedHubs[0], requestedHubs[1], ..., requestedHubs[n-1]]`.
- The shortest distance between two hubs `a` and `b` on a ring of `m` hubs is `min(d, m - d)` where `d = |a - b|`.
- If a requested hub equals the drone's current hub, that leg costs `0`.
### Constraints
- `2 <= m <= 10^9` (the ring can have as few as 2 hubs — handle the `m = 2` ring carefully, where clockwise and counterclockwise distances between the two hubs are equal).
- `1 <= requestedHubs.length <= 10^5`.
- Each entry of `requestedHubs` is an integer in `[1, m]`.
### Input / Output
- **Input:** an integer `m` and an integer array `requestedHubs`.
- **Output:** a single integer — the total minimum delivery time.
Constraints
- 2 <= m <= 10^9
- 1 <= requestedHubs.length <= 10^5
- Each entry of requestedHubs is an integer in [1, m]
- The drone always starts at hub 1
- Per-leg cost is min(|a-b|, m-|a-b|); a leg to the current hub costs 0
Examples
Input: (6, [4, 2])
Expected Output: 5
Explanation: Start at hub 1. Leg 1: 1->4 has |1-4|=3 and 6-3=3, min is 3. Leg 2: 4->2 has |4-2|=2 and 6-2=4, min is 2. Total = 3 + 2 = 5.
Input: (2, [2, 1, 2])
Expected Output: 3
Explanation: Ring of 2 hubs; distance between hub 1 and hub 2 is min(1, 2-1)=1 either way. Legs: 1->2 (1), 2->1 (1), 1->2 (1). Total = 3.
Input: (5, [3])
Expected Output: 2
Explanation: 1->3 has clockwise distance 2 and counterclockwise 3, so min is 2.
Input: (10, [1])
Expected Output: 0
Explanation: The single requested hub equals the start hub 1, so the leg costs 0.
Input: (1000000000, [1000000000, 1, 500000000])
Expected Output: 500000001
Explanation: 1->1e9: |1-1e9|=999999999, wrap = 1, min 1. 1e9->1: min 1. 1->5e8: |1-5e8|=499999999, wrap = 500000001, min 499999999. Total = 1 + 1 + 499999999 = 500000001 (the wraparound short path matters near the ring boundary).
Input: (8, [5, 5])
Expected Output: 4
Explanation: 1->5: |1-5|=4, wrap 8-4=4, min 4. 5->5: same hub, cost 0. Total = 4.
Input: (2, [1, 1, 1])
Expected Output: 0
Explanation: Every requested hub equals the current hub on a 2-hub ring (start at 1, then stay at 1), so all legs cost 0.
Hints
- The drone's choice of clockwise vs counterclockwise is independent per leg, so you can greedily minimize each leg separately — no global optimization is needed.
- On a ring of m hubs, the distance between hubs a and b is min(|a-b|, m-|a-b|). The first term is going the direct way; the second wraps around the ring.
- Track the current hub starting at 1, accumulate the per-leg minimum distance, and update current to the just-visited hub. Watch the m=2 case: |a-b|=1 and m-|a-b|=1 are equal, so the leg costs 1.