Skip to main content
Talentd

Distance Between Bus Stops - Solution & Explanation

EasyArray17 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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^4
  • distance.length == n
  • 0 <= start, destination < n
  • 0 <= 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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), since each direction is evaluated separately only once.
Space Complexity: O(1), using a fixed amount of extra variables.

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Direct Calculation of Clockwise and Counterclockwise Distances

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.

Approach 2: Repeated Combinative Calculation

Time Complexity: O(n), since each direction is evaluated separately only once.
Space Complexity: O(1), using a fixed amount of extra variables.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Clockwise and Counterclockwise CalculationO(n)O(1)Best general solution. Clean logic and minimal passes through the array.
Repeated Combinative CalculationO(n)O(1)Useful when simulating traversal around a circular route or explaining the problem step-by-step.

Video Solution

LeetCode Distance Between Bus Stops Solution Explained - Java • Nick White • 6,976 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Distance Between Bus Stops with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Costs Using the Train Line