Minimum Time to Complete All Deliveries

Minimum Time to Complete All Deliveries

What is this problem about?

The Minimum Time to Complete All Deliveries problem gives you delivery locations on a number line and asks for the minimum total travel time to complete all deliveries and return to the starting point. The challenge is optimizing the route — choosing the order of deliveries to minimize total distance traveled. This Minimum Time to Complete All Deliveries coding problem uses mathematical insight about optimal traversal on a number line.

Why is this asked in interviews?

Amazon asks this to test geometric intuition and mathematical reasoning about optimal movement on a number line. The key insight — that optimal traversal oscillates between the leftmost and rightmost unvisited points — reduces to a clean formula involving intervals. The math and binary search interview pattern applies here, especially for variants requiring range queries.

Algorithmic pattern used

Mathematical formula via sorting. Sort all delivery positions. For positions on both sides of the origin, the minimum travel time equals: 2 * sum of all intervals minus the farthest single reach in one direction. This is because you must traverse each interval at least twice (once going, once returning) except for the final leg, which you traverse only once. Sort the positions, compute interval sums, and apply the formula.

Example explanation

Deliveries at positions: [-3, -1, 2, 5]. Starting at 0.

• Left range: [-3, -1]. Right range: [2, 5].
• Total distance without optimization: 2*(3+1+2+5) = 22.
• Optimal: go right to 5 (cover 2 and 5), then go left to -3 (cover -1 and -3), return to 0.
• Time: 5 (to 5) + 8 (to -3) + 3 (return to 0) = 16. Or go left first: 3+8+5=16.

Common mistakes candidates make

• Simulating all possible routes (exponential complexity).
• Not sorting delivery positions before applying the formula.
• Forgetting to return to the starting point at the end.
• Confusing the "farthest single direction" optimization.

Interview preparation tip

Number-line traversal problems almost always have elegant closed-form solutions based on interval coverage. Sort the positions, think about how many times each segment is crossed, and look for the single "free" direction (the farthest you go in one direction without needing to backtrack). Practice problems involving minimum traversal cost on arrays of positions — they test both geometric intuition and implementation discipline, and are favorites at logistics-focused companies like Amazon.