Distance Between Bus Stops — Solution in Python, Java & C++
Distance Between Bus Stops solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Distance Between Bus Stops is an easy coding problem on arrays and prefix sum, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A bus line is a loop of n stops numbered 0 to n - 1. distance[i] is the length of the road between stop i and stop (i + 1) % n, and the bus may travel the loop in either direction.
Return the length of the shorter way round from stop start to stop destination.
Example 1
Input: distance = [4,1,6,2], start = 3, destination = 1
Output: 6
Explanation: Going 3 → 0 → 1 costs 2 + 4 = 6; going 3 → 2 → 1 costs 6 + 1 = 7.
Example 2
Input: distance = [5,8,2], start = 0, destination = 2
Output: 2
Example 3
Input: distance = [2,5,9,1], start = 1, destination = 1
Output: 0
Constraints
1 <= n <= 10^4distance.length == n0 <= start, destination < n0 <= distance[i] <= 10^4
Hints for Distance Between Bus Stops
Hint 1
There are only two routes: clockwise and counter-clockwise.
Hint 2
The two routes together cover the whole loop exactly once.
Hint 3
Sum the segments between the smaller and the larger stop index; the other route is the loop total minus that.
How to solve Distance Between Bus Stops
The clockwise and counter-clockwise routes split the loop between them, so one sum and the loop's total give both lengths.
Approach
- Let
lo = min(start, destination)andhi = max(start, destination). - Sum
distance[lo..hi-1]— the route that does not cross stop 0's back edge — and the whole array. - Return the smaller of that sum and
total - sum.
Why it works
Travelling from lo up to hi uses exactly the segments lo through hi - 1; the other direction uses every remaining segment. Distance is symmetric, so swapping start and destination changes nothing, and the answer is the smaller of the two complementary sums.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
startmay be larger thandestination— normalise the pair first.- When
start == destinationthe answer is 0. - Segment
ijoins stopito stopi + 1, so the range islotohi - 1, nothi.
Reference solution
Python
from typing import List
def distanceBetweenBusStops(distance: List[int], start: int, destination: int) -> int:
lo, hi = min(start, destination), max(start, destination)
inner = sum(distance[lo:hi])
return min(inner, sum(distance) - inner)Java
public static int distanceBetweenBusStops(int[] distance, int start, int destination) {
int lo = Math.min(start, destination), hi = Math.max(start, destination);
int total = 0, inner = 0;
for (int i = 0; i < distance.length; i++) {
total += distance[i];
if (i >= lo && i < hi) inner += distance[i];
}
return Math.min(inner, total - inner);
}C++
int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
int lo = min(start, destination), hi = max(start, destination);
int total = 0, inner = 0;
for (int i = 0; i < (int)distance.size(); i++) {
total += distance[i];
if (i >= lo && i < hi) inner += distance[i];
}
return min(inner, total - inner);
}JavaScript
var distanceBetweenBusStops = function(distance, start, destination) {
var lo = Math.min(start, destination), hi = Math.max(start, destination);
var total = 0, inner = 0;
for (var i = 0; i < distance.length; i++) {
total += distance[i];
if (i >= lo && i < hi) inner += distance[i];
}
return Math.min(inner, total - inner);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Prefix Sum