The “Distance Between Bus Stops” is a classical problem on Leetcode that belongs to the array category. The problem tests the fundamentals of array manipulation and mathematical reasoning. In this article, we will discuss different approaches to solve this problem, covering their time and space complexities. By the end, you’ll have a comprehensive understanding of how to solve problems related to circular arrays and distance calculations.

## Problem Statement

Before diving into the solution, let’s first understand the problem itself.

### Problem Description

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 numbered `i`

and `i+1`

in the array. You are standing at stop 0. The bus goes to stop `n-1`

and then goes back to stop 0. In other words, the bus moves in a circle.

The task is to return the shortest distance between stops `start`

and `destination`

. You can assume that at most one bus is operating on the circuit. You may choose to travel in either direction around the circle.

### Constraints

`1 <= n <= 10^4`

`distance.length == n`

`1 <= distance[i] <= 10^4`

`0 <= start, destination < n`

## Understanding the Problem

The problem can be thought of as a circular array traversal problem where we can go either clockwise or counter-clockwise. We need to find the shorter distance between the `start`

and `destination`

stops.

## Approaches

### Brute-Force Approach

One naive way to solve this problem is to compute both distances (clockwise and counter-clockwise) between the `start`

and `destination`

stops, and then return the shorter one.

#### Algorithm

- Initialize two variables
`clockwise_distance`

and`counter_clockwise_distance`

to zero. - Traverse the array from the
`start`

index to the`destination`

index in a clockwise manner, summing up distances along the way and store it in`clockwise_distance`

. - Traverse the array from the
`start`

index to the`destination`

index in a counter-clockwise manner, summing up distances along the way and store it in`counter_clockwise_distance`

. - Return the minimum between
`clockwise_distance`

and`counter_clockwise_distance`

.

#### Python Code Implementation

```
def distance_between_bus_stops(distance, start, destination):
n = len(distance)
clockwise_distance = 0
counter_clockwise_distance = 0
# Calculate the clockwise distance
i = start
while i != destination:
clockwise_distance += distance[i]
i = (i + 1) % n
# Calculate the counter-clockwise distance
i = start
while i != destination:
i = (i - 1 + n) % n
counter_clockwise_distance += distance[i]
return min(clockwise_distance, counter_clockwise_distance)
```

#### Time Complexity

The time complexity for this approach is O(n).

#### Space Complexity

The space complexity for this approach is O(1).

### Optimized Approach

We can further optimize our solution. One key observation is that once we calculate the clockwise distance, the counter-clockwise distance is simply the total distance minus the clockwise distance.

#### Algorithm

- Initialize
`clockwise_distance`

to zero. - Traverse the array from the
`start`

index to the`destination`

index in a clockwise manner, summing up distances along the way and store it in`clockwise_distance`

. - Calculate
`total_distance`

by summing up all the elements in the`distance`

array. - Calculate
`counter_clockwise_distance`

by subtracting`clockwise_distance`

from`total_distance`

. - Return the minimum between
`clockwise_distance`

and`counter_clockwise_distance`

.

#### Python Code Implementation

```
def distance_between_bus_stops(distance, start, destination):
n = len(distance)
clockwise_distance = 0
total_distance = sum(distance)
i = start
while i != destination:
clockwise_distance += distance[i]
i = (i + 1) % n
counter_clockwise_distance = total_distance - clockwise_distance
return min(clockwise_distance, counter_clockwise_distance)
```

#### Time Complexity

The time complexity for this approach is O(n).

#### Space Complexity

The space complexity for this approach is O(1).

## Conclusion

The “Distance Between Bus Stops” problem is a classic example of circular array manipulation. While a brute-force approach works well within the constraints, an optimized approach offers a slightly more elegant solution without any real gain in efficiency for this problem’s constraints. Both approaches give us O(n) time complexity and O(1) space complexity.