Distance Between Bus Stops

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

Key Insights

• The bus stops are arranged in a circular manner, allowing traversal in both clockwise and counterclockwise directions.
• The distance between two stops can be calculated in two ways:
  • Clockwise distance from start to destination.
  • Counterclockwise distance from start to destination.
• The minimum of these two distances is the answer.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we will use an array to store the distances between neighboring bus stops. The algorithm follows these steps:

1. Normalize the start and destination indices to ensure that start is always less than or equal to destination.
2. Calculate the total distance of the bus route by summing up all the values in the distance array.
3. Compute the clockwise distance from start to destination by summing the distances between these indices.
4. The counterclockwise distance can be found by subtracting the clockwise distance from the total distance.
5. The result is the minimum of the clockwise and counterclockwise distances.

Code Solutions