LeetCode 1184 - Distance Between Bus Stops

In this problem, we are given a circular bus route with n stops numbered from 0 to n - 1. The array distance describes the distance between neighboring stops. Specifically, distance[i] represents the distance from stop i to stop (i + 1) % n.

leetcodeeasyarray

LeetCode Problem 1184

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

In this problem, we are given a circular bus route with n stops numbered from 0 to n - 1. The array distance describes the distance between neighboring stops. Specifically, distance[i] represents the distance from stop i to stop (i + 1) % n.

Because the route is circular, the bus can travel in two possible directions between any pair of stops:

  • Clockwise
  • Counterclockwise

The task is to compute the shortest possible distance between the start stop and the destination stop.

For example, if:

distance = [1,2,3,4]

then:

  • Distance from 0 -> 1 is 1
  • Distance from 1 -> 2 is 2
  • Distance from 2 -> 3 is 3
  • Distance from 3 -> 0 is 4

If we want to travel from stop 0 to stop 2, there are two routes:

  • Clockwise: 0 -> 1 -> 2, total distance 1 + 2 = 3
  • Counterclockwise: 0 -> 3 -> 2, total distance 4 + 3 = 7

The shortest distance is therefore 3.

The constraints are relatively small:

  • n <= 10^4
  • Each distance value is at most 10^4

This tells us that even an O(n) solution is more than fast enough. The input size is not large enough to require advanced optimization techniques.

There are several important edge cases to keep in mind:

  • start may be greater than destination
  • start and destination may be adjacent
  • The shortest path may actually be the counterclockwise route
  • Some distances may be 0
  • The total route may contain only one stop

The problem guarantees that all stop indices are valid and that the distance array length matches the number of stops.

Approaches

Brute Force Approach

A straightforward solution is to explicitly simulate traveling in both directions.

We can:

  1. Move clockwise from start to destination, accumulating distance
  2. Move counterclockwise from start to destination, accumulating distance
  3. Return the smaller total

This approach is correct because the route is circular, meaning there are exactly two unique paths between any two stops.

Even though this works, the implementation can become slightly messy because counterclockwise traversal requires careful modular arithmetic and wraparound handling.

The runtime is still linear because each traversal touches at most n stops.

Optimal Approach

The key observation is that the two path distances always sum to the total circumference of the circle.

Instead of explicitly traversing both directions, we can:

  1. Compute the distance along one direction
  2. Compute the total distance of the entire circle
  3. Derive the opposite direction distance as:
total_distance - forward_distance

Then we simply return the minimum of the two.

An additional simplification is to ensure:

start <= destination

This allows us to calculate the forward distance using a simple range sum.

This approach is clean, efficient, and easy to reason about.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Simulates both clockwise and counterclockwise traversal directly
Optimal O(n) O(1) Computes one path and derives the other using total sum

Algorithm Walkthrough

  1. First, ensure that start is less than or equal to destination.

This normalization simplifies the traversal logic. If start > destination, we swap them. After swapping, the clockwise route from start to destination corresponds to the contiguous subarray:

distance[start:destination]
  1. Compute the total distance around the circle.

We sum all values in the distance array. This represents the full circumference of the route. 3. Compute the clockwise distance.

We sum all distances from index start up to, but not including, destination.

This gives the distance when moving directly forward through the array. 4. Compute the counterclockwise distance.

Since the entire circle distance is known, the opposite route distance is:

total_distance - clockwise_distance
  1. Return the smaller value.

The shortest path must be one of the two possible directions, so we return:

min(clockwise_distance, counterclockwise_distance)

Why it works

A circular route always provides exactly two distinct paths between two stops. Every edge belongs to exactly one of those two paths. Therefore:

clockwise_distance + counterclockwise_distance = total_circle_distance

By computing one path and subtracting from the total, we obtain the other path exactly. Taking the minimum guarantees the shortest valid route.

Python Solution

from typing import List

class Solution:
    def distanceBetweenBusStops(self, distance: List[int], start: int, destination: int) -> int:
        if start > destination:
            start, destination = destination, start

        clockwise_distance = sum(distance[start:destination])
        total_distance = sum(distance)

        counterclockwise_distance = total_distance - clockwise_distance

        return min(clockwise_distance, counterclockwise_distance)

The implementation begins by normalizing the indices so that start <= destination. This allows the clockwise path to be represented directly as a contiguous slice of the array.

Next, the code computes the clockwise distance using:

sum(distance[start:destination])

This works because each element represents the edge between consecutive stops.

The total circle distance is then computed using sum(distance).

Since the counterclockwise path contains all remaining edges, its distance is simply:

total_distance - clockwise_distance

Finally, the algorithm returns the smaller of the two possible path lengths.

Go Solution

func distanceBetweenBusStops(distance []int, start int, destination int) int {
    if start > destination {
        start, destination = destination, start
    }

    clockwiseDistance := 0
    totalDistance := 0

    for i, d := range distance {
        totalDistance += d

        if i >= start && i < destination {
            clockwiseDistance += d
        }
    }

    counterclockwiseDistance := totalDistance - clockwiseDistance

    if clockwiseDistance < counterclockwiseDistance {
        return clockwiseDistance
    }

    return counterclockwiseDistance
}

The Go implementation follows the same logic as the Python solution. Since Go does not provide built in slice summation utilities like Python's sum(), the implementation computes both totals inside a single loop.

Go slices are reference based, but this problem only requires reading values, so there are no mutation concerns. Integer overflow is not an issue because the maximum possible total distance is well within Go's int range.

Worked Examples

Example 1

distance = [1,2,3,4]
start = 0
destination = 1

After normalization:

start = 0
destination = 1

Compute totals:

Step Value
Total distance 1 + 2 + 3 + 4 = 10
Clockwise distance distance[0:1] = 1
Counterclockwise distance 10 - 1 = 9
Result min(1, 9) = 1

Final answer:

1

Example 2

distance = [1,2,3,4]
start = 0
destination = 2
Step Value
Total distance 10
Clockwise distance 1 + 2 = 3
Counterclockwise distance 10 - 3 = 7
Result min(3, 7) = 3

Final answer:

3

Example 3

distance = [1,2,3,4]
start = 0
destination = 3
Step Value
Total distance 10
Clockwise distance 1 + 2 + 3 = 6
Counterclockwise distance 10 - 6 = 4
Result min(6, 4) = 4

Final answer:

4

Complexity Analysis

Measure Complexity Explanation
Time O(n) We iterate through the distance array a constant number of times
Space O(1) Only a few integer variables are used

The algorithm performs linear work proportional to the number of bus stops. No auxiliary data structures are allocated, so the memory usage remains constant regardless of input size.

Test Cases

from typing import List

class Solution:
    def distanceBetweenBusStops(self, distance: List[int], start: int, destination: int) -> int:
        if start > destination:
            start, destination = destination, start

        clockwise_distance = sum(distance[start:destination])
        total_distance = sum(distance)

        return min(clockwise_distance, total_distance - clockwise_distance)

solution = Solution()

assert solution.distanceBetweenBusStops([1,2,3,4], 0, 1) == 1  # adjacent stops
assert solution.distanceBetweenBusStops([1,2,3,4], 0, 2) == 3  # clockwise shorter
assert solution.distanceBetweenBusStops([1,2,3,4], 0, 3) == 4  # counterclockwise shorter
assert solution.distanceBetweenBusStops([1,2,3,4], 3, 0) == 4  # start > destination
assert solution.distanceBetweenBusStops([5], 0, 0) == 0  # single stop
assert solution.distanceBetweenBusStops([0,0,0], 0, 2) == 0  # zero distances
assert solution.distanceBetweenBusStops([7,1,5,2], 1, 3) == 6  # normal middle traversal
assert solution.distanceBetweenBusStops([10,20,30], 1, 1) == 0  # same start and destination
assert solution.distanceBetweenBusStops([2,2,2,2], 0, 2) == 4  # equal routes
assert solution.distanceBetweenBusStops([10000]*10000, 0, 5000) == 50000000  # large input
Test Why
[1,2,3,4], 0 -> 1 Validates adjacent stop handling
[1,2,3,4], 0 -> 2 Verifies normal clockwise shortest path
[1,2,3,4], 0 -> 3 Verifies counterclockwise shortest path
[1,2,3,4], 3 -> 0 Ensures swapping logic works
[5], 0 -> 0 Smallest possible input
[0,0,0], 0 -> 2 Handles zero edge weights
[7,1,5,2], 1 -> 3 General nontrivial traversal
[10,20,30], 1 -> 1 Same start and destination
[2,2,2,2], 0 -> 2 Both paths equal length
Large repeated values Stress test for performance and correctness

Edge Cases

Start and destination are the same

If start == destination, the shortest distance should be 0 because no travel is needed.

A buggy implementation might accidentally traverse the entire circle and return the total distance instead. In this solution, the slice:

distance[start:destination]

becomes empty, producing a clockwise distance of 0, which correctly leads to the final answer 0.

Start index is greater than destination index

For example:

start = 3
destination = 1

Without normalization, computing the clockwise path becomes awkward because the traversal wraps around the end of the array.

The implementation avoids this complexity by swapping the values when start > destination. This transforms the problem into a simple contiguous range sum.

The shortest path is counterclockwise

A common mistake is assuming the direct forward traversal is always optimal.

For example:

distance = [1,2,3,4]
start = 0
destination = 3

The clockwise route is:

1 + 2 + 3 = 6

but the counterclockwise route is only:

4

The algorithm correctly handles this by explicitly comparing both possible route distances.