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.
This approach involves calculating the total distance in the array and the clockwise distance from the start to the destination. The counterclockwise distance can be calculated by subtracting the clockwise distance from the total distance. The shortest path is the minimum of these two values.
This C program calculates the shortest distance between start and destination bus stops. We first determine direct distances in forward direction and sum them, and then we calculate the clockwise distance by iterating over the respective segment of the array. The function returns the smaller of the two calculated values, ensuring the shortest path is selected.
Time Complexity: O(n), where n is the number of bus stops.
Space Complexity: O(1), as no extra space is utilized apart from the input.
This approach tries to build the distance in both directions independently and simultaneously, allowing us to directly determine the shorter path without calculating the total peripherical distance.
In this C program, the shortest bus stop distance is calculated directly by simultaneously evaluating the clockwise and counterclockwise distances. This technique utilizes two loops, advancing one index each time, and the shortest distance is selected.
Time Complexity: O(n), since each direction is evaluated separately only once.
Space Complexity: O(1), using a fixed amount of extra variables.
We can first calculate the total distance s that the bus travels, then simulate the bus's journey. Starting from the departure point, we move one stop to the right each time until we reach the destination, recording the travel distance t during this process. Finally, we return the minimum value between t and s - t.
The time complexity is O(n), where n is the length of the array distance. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Direct Calculation of Clockwise and Counterclockwise Distances | Time Complexity: O(n), where n is the number of bus stops. |
| Approach 2: Repeated Combinative Calculation | Time Complexity: O(n), since each direction is evaluated separately only once. |
| Simulation | — |
| 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. |
LeetCode Distance Between Bus Stops Solution Explained - Java • Nick White • 6,959 views views
Watch 9 more video solutions →Practice Distance Between Bus Stops with our built-in code editor and test cases.
Practice on FleetCode