Watch 10 video solutions for Distance Between Bus Stops, a easy level problem involving Array. This walkthrough by Nick White has 6,959 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A bus has n stops numbered from 0 to n - 1 that form a circle. We know the distance between all pairs of neighboring stops where distance[i] is the distance between the stops number i and (i + 1) % n.
The bus goes along both directions i.e. clockwise and counterclockwise.
Return the shortest distance between the given start and destination stops.
Example 1:
Input: distance = [1,2,3,4], start = 0, destination = 1 Output: 1 Explanation: Distance between 0 and 1 is 1 or 9, minimum is 1.
Example 2:
Input: distance = [1,2,3,4], start = 0, destination = 2 Output: 3 Explanation: Distance between 0 and 2 is 3 or 7, minimum is 3.
Example 3:
Input: distance = [1,2,3,4], start = 0, destination = 3 Output: 4 Explanation: Distance between 0 and 3 is 6 or 4, minimum is 4.
Constraints:
1 <= n <= 10^4distance.length == n0 <= start, destination < n0 <= distance[i] <= 10^4Problem Overview: You are given a circular route of bus stops where distance[i] represents the distance from stop i to i+1. Given two stops start and destination, compute the shortest distance along the circle. Because the route is circular, you can travel either clockwise or counterclockwise.
Approach 1: Direct Calculation of Clockwise and Counterclockwise Distances (O(n) time, O(1) space)
This approach directly models the two possible paths between the stops. First, ensure start < destination by swapping if necessary. Iterate through the array once and accumulate two values: the distance from start to destination (clockwise segment) and the total distance of the entire circle. The counterclockwise distance is simply total - clockwise. The answer is min(clockwise, total - clockwise). The key insight is that any path between the two stops must be one of these two segments of the circle, so computing both guarantees the optimal result.
This solution runs in O(n) time because it scans the array once and uses O(1) extra space. It is straightforward and typically what interviewers expect for this problem because it leverages basic iteration and arithmetic over an array.
Approach 2: Repeated Combinative Calculation (O(n) time, O(1) space)
This method simulates movement around the circular route. Starting from start, repeatedly add distances while moving forward until reaching destination. That gives the clockwise path length. Then compute the total distance of the route and subtract the clockwise value to obtain the counterclockwise path. Finally, return the smaller of the two.
The logic emphasizes step-by-step accumulation along the circular structure. Instead of splitting the array into segments immediately, you compute distances through repeated additions. Conceptually, this mirrors how you would traverse a circular list or ring buffer in many array-based problems. Time complexity remains O(n) because at most the full array is traversed once, and space complexity stays O(1).
Recommended for interviews: The direct clockwise/counterclockwise calculation is the expected solution. It demonstrates that you recognize the circular structure and reduce the problem to two deterministic path sums. The repeated accumulation approach still works, but the direct method communicates the insight faster and keeps the implementation cleaner.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Clockwise and Counterclockwise Calculation | O(n) | O(1) | Best general solution. Clean logic and minimal passes through the array. |
| Repeated Combinative Calculation | O(n) | O(1) | Useful when simulating traversal around a circular route or explaining the problem step-by-step. |