Problem Description

The "Distance Between Bus Stops" problem asks you to determine the shortest distance between two bus stops on a circular route.

You are given:

• A list called distance, where distance[i] represents the distance between the i-th bus stop and the next stop ((i+1)th stop). The bus stops are arranged in a circle.
• Two integers, start and destination, which are indices of the starting and ending bus stops.

• There is always at least one valid solution.
• The bus stops form a circle, so after the last stop, the next stop is the first one.
• You cannot reuse the same segment twice in the same path.

Thought Process

The first idea that comes to mind is to try both possible routes between the start and destination stops: one going clockwise and the other counterclockwise. Since the route is circular, these are the only two possibilities.

A brute-force approach would be to simulate both paths by summing up the distances along each possible direction and then return the smaller of the two sums.

However, we can optimize this process by realizing that the sum of the clockwise path and the counterclockwise path will always add up to the total distance around the circle. So, if we compute the total distance and one of the path distances, the other is simply the total minus the first path. This insight allows us to avoid redundant calculations.

Solution Approach

Let's break down the steps to solve the problem efficiently:

1. Normalize the Indices:
   Since the bus stops are in a circle, ensure that start is less than destination. If not, swap them. This makes it easier to sum the distances between them in one direction.
2. Compute Clockwise Distance:
   Sum the distances from start up to (but not including) destination. This represents the clockwise path.
3. Compute Total Distance:
   Sum all the values in the distance array. This is the total length of the circular route.
4. Get Counterclockwise Distance:
   Subtract the clockwise path from the total distance to get the counterclockwise path.
5. Return the Shortest Path:
   Return the smaller value between the clockwise and counterclockwise distances.

Example Walkthrough

Let's consider a sample input:
distance = [1, 2, 3, 4], start = 0, destination = 2

Step-by-step:

• First, since start (0) < destination (2), we don't need to swap.
• Clockwise path: sum distance[0] and distance[1] (i.e., stops 0→1 and 1→2): 1 + 2 = 3
• Total distance: 1 + 2 + 3 + 4 = 10
• Counterclockwise path: 10 - 3 = 7
• Shortest distance: min(3, 7) = 3

Time and Space Complexity

Brute-force Approach:

• Time Complexity: O(n) for each direction, so overall O(n).
• Space Complexity: O(1), since only variables are used.

• Time Complexity: O(n), since we make two passes through the distance array (one for the clockwise sum, one for the total sum).
• Space Complexity: O(1), as only a few integer variables are used.

Summary

To solve the "Distance Between Bus Stops" problem, we leveraged the circular nature of the bus route. By calculating the distance in one direction and subtracting it from the total to get the other direction, we efficiently found the shortest path. This approach is both simple and optimal, requiring only two passes through the data and no extra space. The key insight is recognizing that the two possible paths always sum to the total distance, allowing for a quick calculation of the shortest route.

Code Implementation

class Solution:
    def distanceBetweenBusStops(self, distance, start, destination):
        # Ensure start < destination for easier calculation
        if start > destination:
            start, destination = destination, start
        # Clockwise distance
        clockwise = sum(distance[start:destination])
        # Total distance
        total = sum(distance)
        # Counterclockwise distance
        counterclockwise = total - clockwise
        return min(clockwise, counterclockwise)
      

class Solution {
public:
    int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
        if (start > destination) swap(start, destination);
        int clockwise = 0, total = 0;
        for (int i = 0; i < distance.size(); ++i) {
            total += distance[i];
            if (i >= start && i < destination) {
                clockwise += distance[i];
            }
        }
        int counterclockwise = total - clockwise;
        return min(clockwise, counterclockwise);
    }
};
      

class Solution {
    public int distanceBetweenBusStops(int[] distance, int start, int destination) {
        if (start > destination) {
            int temp = start;
            start = destination;
            destination = temp;
        }
        int clockwise = 0, total = 0;
        for (int i = 0; i < distance.length; i++) {
            total += distance[i];
            if (i >= start && i < destination) {
                clockwise += distance[i];
            }
        }
        int counterclockwise = total - clockwise;
        return Math.min(clockwise, counterclockwise);
    }
}
      

var distanceBetweenBusStops = function(distance, start, destination) {
    if (start > destination) {
        [start, destination] = [destination, start];
    }
    let clockwise = 0, total = 0;
    for (let i = 0; i < distance.length; i++) {
        total += distance[i];
        if (i >= start && i < destination) {
            clockwise += distance[i];
        }
    }
    let counterclockwise = total - clockwise;
    return Math.min(clockwise, counterclockwise);
};