Distance Between Bus Stops solution and explanation
Google
9 more videos on this problem
LeetCode Distance Between Bus Stops Solution Explained - JavaNick White · 6:46 · 6K views
LeetCode 1184: Distance Between Bus Stops - Interview Prep Ep 15Fisher Coder · 13:26 · 1K views
Distance Between Bus Stops | Leetcode 1184 | Amazon Google Facebook interview questionSuper Lazy Coder · 7:14 · 911 views
Vol64 - Leetcode - Problem 1184 - Distance between bus stops - Golang - Phỏng vấn - Thuật toánYuh lập trình viên · 10:02 · 844 views
1184. Distance Between Bus Stops (Leetcode Easy)Programming Live with Larry · 7:44 · 275 views
Leetcode 1184. Distance Between Bus Stops (Solution + Explanation)ultcode · 5:09 · 215 views
Distance Between Bus Stops (Leetcode 1184)Algorithms Casts · 23:28 · 190 views
LeetCode in JavaScript - Distance between Bus StopsSayantan Codes · 10:54 · 153 views
Leetcode solving: 1184. Distance Between Bus StopsMath Geeks · 1:49 · 128 views
LeetCode Çözümleri - 1184. Distance Between Bus StopsSoner Gönül · 11:54 · 127 views
The problem
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^4
Approach overview
Problem 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 1: Approach 1: Direct Calculation of Clockwise and Counterclockwise Distances
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.
def distanceBetweenBusStops(distance, start, destination):
if start > destination:
start, destination = destination, start
total_distance = sum(distance)
clockwise_distance = sum(distance[start:destination])
return min(clockwise_distance, total_distance - clockwise_distance)
if __name__ == "__main__":
distance = [1, 2, 3, 4]
start = 0
destination = 3
print(distanceBetweenBusStops(distance, start, destination))class Solution {
public int distanceBetweenBusStops(int[] distance, int start, int destination) {
if (start > destination) {
int temp = start;
start = destination;
destination = temp;
}
int totalDist = 0, clockwiseDist = 0;
for (int i = 0; i < distance.length; i++) {
totalDist += distance[i];
if (i >= start && i < destination) {
clockwiseDist += distance[i];
}
}
return Math.min(clockwiseDist, totalDist - clockwiseDist);
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] distance = {1, 2, 3, 4};
int start = 0;
int destination = 3;
System.out.println(sol.distanceBetweenBusStops(distance, start, destination));
}
}#include <iostream>
#include <vector>
using namespace std;
int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
if (start > destination) swap(start, destination);
int totalDist = 0, clockwiseDist = 0;
for (int i = 0; i < distance.size(); ++i) {
totalDist += distance[i];
if (i >= start && i < destination) {
clockwiseDist += distance[i];
}
}
return min(clockwiseDist, totalDist - clockwiseDist);
}
int main() {
vector<int> distance = {1, 2, 3, 4};
int start = 0, destination = 3;
cout << distanceBetweenBusStops(distance, start, destination) << endl;
return 0;
}function distanceBetweenBusStops(distance, start, destination) {
if (start > destination) [start, destination] = [destination, start];
let totalDistance = distance.reduce((a, b) => a + b, 0);
let clockwiseDistance = distance.slice(start, destination).reduce((a, b) => a + b, 0);
return Math.min(clockwiseDistance, totalDistance - clockwiseDistance);
}
const distance = [1, 2, 3, 4];
const start = 0;
const destination = 3;
console.log(distanceBetweenBusStops(distance, start, destination));#include <stdio.h>
int distanceBetweenBusStops(int* distance, int distanceSize, int start, int destination){
if (start > destination) {
int temp = start;
start = destination;
destination = temp;
}
int clockwiseDist = 0, totalDist = 0;
for (int i = 0; i < distanceSize; i++) {
totalDist += distance[i];
if (i >= start && i < destination) {
clockwiseDist += distance[i];
}
}
return clockwiseDist < (totalDist - clockwiseDist) ? clockwiseDist : (totalDist - clockwiseDist);
}
int main() {
int distance[] = {1, 2, 3, 4};
int start = 0;
int destination = 3;
int result = distanceBetweenBusStops(distance, 4, start, destination);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public int DistanceBetweenBusStops(int[] distance, int start, int destination) {
if (start > destination) {
int temp = start;
start = destination;
destination = temp;
}
int totalDist = 0, clockwiseDist = 0;
for (int i = 0; i < distance.Length; i++) {
totalDist += distance[i];
if (i >= start && i < destination) {
clockwiseDist += distance[i];
}
}
return Math.Min(clockwiseDist, totalDist - clockwiseDist);
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] distance = new int[] {1, 2, 3, 4};
int start = 0, destination = 3;
Console.WriteLine(solution.DistanceBetweenBusStops(distance, start, destination));
}
}This Python code calculates the shortest distance between two bus stops. First, it calculates the total distance of the circle, then computes the clockwise distance directly. The counterclockwise distance is implicitly calculated as the total distance minus the clockwise distance; the minimum of these two is returned.
Time Complexity: O(n) as it scans through the list and sums it twice.
Space Complexity: O(1), because it uses constant additional space.
Approach 2: Approach 2: Repeated Combinative Calculation
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.
def distanceBetweenBusStops(distance, start, destination):
n = len(distance)
clockwise_distance = 0
counterclockwise_distance = 0
if start > destination:
start, destination = destination, start
# Calculate clockwise distance
i = start
while i != destination:
clockwise_distance += distance[i]
i = (i + 1) % n
# Calculate counterclockwise distance
i = destination
while i != start:
counterclockwise_distance += distance[i]
i = (i + 1) % n
return min(clockwise_distance, counterclockwise_distance)
if __name__ == "__main__":
distance = [1, 2, 3, 4]
start = 0
destination = 3
print(distanceBetweenBusStops(distance, start, destination))class Solution {
public int distanceBetweenBusStops(int[] distance, int start, int destination) {
int n = distance.length;
int clockwiseDist = 0, counterclockwiseDist = 0;
if (start > destination) {
int temp = start;
start = destination;
destination = temp;
}
for (int i = start; i != destination; i = (i + 1) % n) {
clockwiseDist += distance[i];
}
for (int i = destination; i != start; i = (i + 1) % n) {
counterclockwiseDist += distance[i];
}
return Math.min(clockwiseDist, counterclockwiseDist);
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] distance = {1, 2, 3, 4};
int start = 0;
int destination = 3;
System.out.println(sol.distanceBetweenBusStops(distance, start, destination));
}
}#include <iostream>
#include <vector>
using namespace std;
int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
int clockwiseDist = 0, counterclockwiseDist = 0, n = distance.size();
if (start > destination) swap(start, destination);
for (int i = start; i != destination; i = (i + 1) % n) {
clockwiseDist += distance[i];
}
for (int i = destination; i != start; i = (i + 1) % n) {
counterclockwiseDist += distance[i];
}
return min(clockwiseDist, counterclockwiseDist);
}
int main() {
vector<int> distance = {1, 2, 3, 4};
int start = 0, destination = 3;
cout << distanceBetweenBusStops(distance, start, destination) << endl;
return 0;
}function distanceBetweenBusStops(distance, start, destination) {
let n = distance.length;
let clockwiseDistance = 0, counterclockwiseDistance = 0;
if (start > destination) [start, destination] = [destination, start];
for (let i = start; i !== destination; i = (i + 1) % n) {
clockwiseDistance += distance[i];
}
for (let i = destination; i !== start; i = (i + 1) % n) {
counterclockwiseDistance += distance[i];
}
return Math.min(clockwiseDistance, counterclockwiseDistance);
}
const distance = [1, 2, 3, 4];
const start = 0;
const destination = 3;
console.log(distanceBetweenBusStops(distance, start, destination));#include <stdio.h>
int distanceBetweenBusStops(int* distance, int distanceSize, int start, int destination){
if (start > destination) {
int temp = start;
start = destination;
destination = temp;
}
int clockwiseDist = 0, counterclockwiseDist = 0;
for (int i = start; i != destination; i = (i + 1) % distanceSize) {
clockwiseDist += distance[i];
}
for (int i = destination; i != start; i = (i + 1) % distanceSize) {
counterclockwiseDist += distance[i];
}
return clockwiseDist < counterclockwiseDist ? clockwiseDist : counterclockwiseDist;
}
int main() {
int distance[] = {1, 2, 3, 4};
int start = 0;
int destination = 3;
int result = distanceBetweenBusStops(distance, 4, start, destination);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public int DistanceBetweenBusStops(int[] distance, int start, int destination) {
int n = distance.Length;
int clockwiseDist = 0, counterclockwiseDist = 0;
if (start > destination) {
int temp = start;
start = destination;
destination = temp;
}
for (int i = start; i != destination; i = (i + 1) % n) {
clockwiseDist += distance[i];
}
for (int i = destination; i != start; i = (i + 1) % n) {
counterclockwiseDist += distance[i];
}
return Math.Min(clockwiseDist, counterclockwiseDist);
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] distance = new int[] {1, 2, 3, 4};
int start = 0;
int destination = 3;
Console.WriteLine(solution.DistanceBetweenBusStops(distance, start, destination));
}
}This Python function iteratively calculates distance traveling both clock and counterclockwise, using distinct loops for each method. Simple tests are run to confirm the smaller result. This direct path ensures an efficient determination of the shortest distance.
Time Complexity: O(n), as both directional scans are taken independently.
Space Complexity: O(1), with low auxiliary variable use.
Approach 3: Simulation
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).
function distanceBetweenBusStops(distance: number[], start: number, destination: number): number {
const s = distance.reduce((a, b) => a + b, 0);
const n = distance.length;
let t = 0;
while (start !== destination) {
t += distance[start];
start = (start + 1) % n;
}
return Math.min(t, s - t);
}func distanceBetweenBusStops(distance []int, start int, destination int) int {
s, t := 0, 0
for _, x := range distance {
s += x
}
for start != destination {
t += distance[start]
start = (start + 1) % len(distance)
}
return min(t, s-t)
}impl Solution {
pub fn distance_between_bus_stops(distance: Vec<i32>, start: i32, destination: i32) -> i32 {
let s: i32 = distance.iter().sum();
let mut t = 0;
let n = distance.len();
let mut start = start as usize;
let destination = destination as usize;
while start != destination {
t += distance[start];
start = (start + 1) % n;
}
t.min(s - t)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Direct Calculation of Clockwise and Counterclockwise Distances | Time Complexity: O(n) as it scans through the list and sums it twice. |
| Approach 2: Repeated Combinative Calculation | Time Complexity: O(n), as both directional scans are taken independently. |
| Simulation | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Distance Between Bus Stops easy or hard?
Distance Between Bus Stops is categorized as an Easy problem on LeetCode with an acceptance rate above 50%. It mainly tests understanding of array traversal and recognizing that a circular path has exactly two possible routes between any two points.
How to solve Distance Between Bus Stops in O(n)?
Iterate through the distance array and compute two values: the total distance of the circular route and the distance between start and destination when traveling clockwise. The counterclockwise distance is total minus clockwise. Return the smaller of these two values. The array is scanned once, giving O(n) time complexity.
Distance Between Bus Stops Python or Java solution?
Both Python and Java implementations follow the same idea: iterate through the distance array, compute the clockwise segment, calculate the total distance, and return the minimum of clockwise and counterclockwise values. The logic remains identical across languages and runs in O(n) time with O(1) space.
What is the best approach for Distance Between Bus Stops?
The most efficient approach computes both possible paths between the two stops: the clockwise segment and the counterclockwise segment. First sum the distances between start and destination, then compute the total route distance and subtract the clockwise segment to get the alternative path. The result is the minimum of the two. This runs in O(n) time and O(1) space.
What data structure is used in Distance Between Bus Stops?
The primary data structure is an array that stores distances between adjacent bus stops. The algorithm iterates through this array and performs simple arithmetic operations to compute path lengths. No additional data structures are required.
What is the time complexity of Distance Between Bus Stops?
The optimal solution runs in O(n) time where n is the number of bus stops. The algorithm performs a single pass through the distance array to compute segment and total distances. Space complexity remains O(1) because only a few integer variables are used.
Is Distance Between Bus Stops asked at Google, Amazon, or Meta?
This problem represents a typical array traversal and circular path calculation question. Variants of circular distance and ring traversal problems appear in interviews at companies like Amazon and Google, especially in early algorithm rounds focused on arrays and basic logic.