Distance Between Bus Stops
Problem
A bus travels along a circular route. The array distance gives the distance between stop i and stop (i + 1) % n. Given a start and a destination stop, return the shortest distance the bus must travel — it may go clockwise or counterclockwise.
distance = [1, 2, 3, 4], start = 0, destination = 23def distance_between_bus_stops(distance, start, destination):
if start > destination:
start, destination = destination, start
clockwise = sum(distance[start:destination])
total = sum(distance)
return min(clockwise, total - clockwise)function distanceBetweenBusStops(distance, start, destination) {
if (start > destination) [start, destination] = [destination, start];
let clockwise = 0, total = 0;
for (let i = 0; i < distance.length; i++) {
total += distance[i];
if (i >= start && i < destination) clockwise += distance[i];
}
return Math.min(clockwise, total - clockwise);
}class Solution {
public int distanceBetweenBusStops(int[] distance, int start, int destination) {
if (start > destination) { int t = start; start = destination; destination = t; }
int clockwise = 0, total = 0;
for (int i = 0; i < distance.length; i++) {
total += distance[i];
if (i >= start && i < destination) clockwise += distance[i];
}
return Math.min(clockwise, total - clockwise);
}
}int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
if (start > destination) swap(start, destination);
int clockwise = 0, total = 0;
for (int i = 0; i < (int)distance.size(); i++) {
total += distance[i];
if (i >= start && i < destination) clockwise += distance[i];
}
return min(clockwise, total - clockwise);
}Explanation
On a circular route there are only two ways to get from one stop to another: go clockwise or go the other way around the loop. The key insight is that these two paths together cover the entire circle, so once we know one of them, the other is just the total minus it.
First we make sure start is the smaller index by swapping if needed. This is safe because the distance is the same no matter which direction you call "start". Now the clockwise path is simply the sum of the edges between start and destination.
We add up distance[start:destination] for the clockwise arc, and we also compute total, the sum of every edge. The counterclockwise path is then total - clockwise.
The answer is the smaller of the two: min(clockwise, total - clockwise).
Example: distance = [1, 2, 3, 4], start = 0, destination = 2. Clockwise covers edges 0 and 1 → 1 + 2 = 3. Total is 10, so counterclockwise is 10 - 3 = 7. The minimum is 3.