# Distance Between Bus Stops
**Difficulty:** EASY
[External](https://leetcode.com/problems/distance-between-bus-stops)
Canonical: https://scaleengineer.com/dsa/problems/distance-between-bus-stops
**Data structures:** Array
---
## Problem
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:**

![](https://assets.glich.co/dsa/distance-between-bus-stops/image0.jpg)

**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:**

![](https://assets.glich.co/dsa/distance-between-bus-stops/image1.jpg)

**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:**

![](https://assets.glich.co/dsa/distance-between-bus-stops/image2.jpg)

**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`

# Approaches
## Graph Traversal with Dijkstra's Algorithm
This approach models the circular bus route as a graph. Each bus stop is a node (vertex), and the path between adjacent stops is an edge with a weight equal to the distance. The problem then becomes finding the shortest path between the `start` and `destination` nodes in this graph. Since all distances (edge weights) are non-negative, Dijkstra's algorithm is a suitable choice for finding the shortest path.
**Time:** O(n log n). Building the graph takes O(n). Dijkstra's algorithm with a binary heap priority queue runs in O(E log V), where V=n (vertices) and E=2n (edges). This results in a complexity of O(n log n). · **Space:** O(n), where n is the number of stops. The adjacency list requires O(n) space, and Dijkstra's algorithm uses a distance array and a priority queue, both of which can take up to O(n) space.
**Pros:** It is a general and robust algorithm for solving shortest path problems on graphs with non-negative edge weights.; Guaranteed to find the correct shortest path.
**Cons:** Overly complex for this specific problem, as the graph structure is a simple cycle.; Less efficient in terms of time and space complexity compared to a direct calculation.
### Explanation
The problem can be generalized as finding the shortest path in an undirected, weighted graph. Dijkstra's algorithm is a classic algorithm for this purpose.

*   **Graph Representation:** We first build an adjacency list to represent the circular connections. For each stop `i`, there's a path to `(i + 1) % n` and vice-versa, with the weight `distance[i]`.
*   **Initialization:** We use a distance array `dist` to store the shortest distance from `start` to every other stop, initialized to infinity. A priority queue helps in efficiently selecting the next stop to visit based on the shortest known distance.
*   **Pathfinding:** The algorithm iteratively explores the graph, always expanding from the unvisited stop with the smallest distance. When it explores a stop `u`, it checks all its neighbors `v` and updates their distances if a shorter path is found via `u`. This process is called edge relaxation.
*   **Result:** Once the `destination` stop is reached and extracted from the priority queue, its distance is guaranteed to be the shortest possible from the `start` stop.

Here is a Java implementation of this approach:
```java
import java.util.*;

class Solution {
    public int distanceBetweenBusStops(int[] distance, int start, int destination) {
        int n = distance.length;
        if (start == destination) return 0;

        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < n; i++) {
            int u = i;
            int v = (i + 1) % n;
            int w = distance[i];
            adj.get(u).add(new int[]{v, w});
            adj.get(v).add(new int[]{u, w});
        }

        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        // Priority Queue stores {distance, node}
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{0, start});

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int d = current[0];
            int u = current[1];

            if (u == destination) {
                return d;
            }

            if (d > dist[u]) {
                continue;
            }

            for (int[] edge : adj.get(u)) {
                int v = edge[0];
                int weight = edge[1];
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }
        return -1; // Should not be reached given the problem constraints
    }
}
```
### Algorithm
*   **Graph Representation:** Model the bus stops as a graph where each stop is a vertex. For each stop `i`, create a weighted, undirected edge between vertex `i` and vertex `(i + 1) % n` with the weight being `distance[i]`.
*   **Initialization:** Create a distance array, `dist`, of size `n` and initialize all values to infinity, except for the `start` vertex, which is set to 0. Use a priority queue to store pairs of `(distance, vertex)` and add `(0, start)` to it.
*   **Dijkstra's Execution:** While the priority queue is not empty, extract the vertex `u` with the smallest distance.
*   **Relax Edges:** For each neighbor `v` of `u`, if the path through `u` is shorter than the known distance to `v` (i.e., `dist[u] + weight(u, v) < dist[v]`), update `dist[v]` and add the new pair `(dist[v], v)` to the priority queue.
*   **Termination:** The algorithm can terminate as soon as the `destination` vertex is extracted from the priority queue, as this will be its shortest path. The distance associated with it is the answer.

## Single Pass Calculation
This approach leverages the simple circular nature of the bus route. There are only two paths between any two stops: one clockwise and one counter-clockwise. The key insight is that the sum of the lengths of these two paths is always equal to the total distance of the entire circular route. Instead of complex graph algorithms, we can calculate the distances of both paths in a single loop over the `distance` array and then find the minimum.
**Time:** O(n), where n is the number of stops. We perform a single pass through the `distance` array of length `n`. · **Space:** O(1). We only use a few variables to store the calculated distances, regardless of the input size.
**Pros:** Optimal time complexity, as it only requires a single pass through the input array.; Optimal space complexity, using only a constant amount of extra space.; Simple to understand and implement.
**Cons:** This solution is highly specific to the problem's circular structure and is not a general-purpose shortest path algorithm.
### Explanation
This method is a direct and efficient way to solve the problem by calculating the two possible path distances and comparing them.

*   **Path Definition:** The path from `start` to `destination` can be thought of as two segments on the circle. If we assume `start < destination`, one path covers indices from `start` to `destination - 1`, and the other path covers the remaining indices.
*   **Simultaneous Calculation:** We can iterate through the entire `distance` array once. Using a simple conditional check, we can determine which of the two paths each `distance[i]` segment belongs to and add it to the corresponding running total (`clockwiseDist` or `counterClockwiseDist`).
*   **Result:** This single pass efficiently computes both path lengths. The final step is to return the smaller of the two calculated distances.

This approach is optimal as it requires visiting each distance value only once.

Here is a concise Java implementation:
```java
class Solution {
    public int distanceBetweenBusStops(int[] distance, int start, int destination) {
        // To simplify the logic, ensure start is always less than destination.
        if (start > destination) {
            int temp = start;
            start = destination;
            destination = temp;
        }
        
        int clockwiseDist = 0;
        int counterClockwiseDist = 0;
        
        for (int i = 0; i < distance.length; i++) {
            // The path from start to destination in increasing index order
            if (i >= start && i < destination) {
                clockwiseDist += distance[i];
            } else { // The other path
                counterClockwiseDist += distance[i];
            }
        }
        
        return Math.min(clockwiseDist, counterClockwiseDist);
    }
}
```
### Algorithm
*   **Normalize Indices:** To simplify the logic, ensure that `start` is less than `destination`. If `start > destination`, swap their values. This does not change the distance between them.
*   **Initialize Distances:** Create two variables, `clockwiseDist` and `counterClockwiseDist`, and initialize both to 0.
*   **Single Pass:** Iterate through the `distance` array from index `i = 0` to `n-1`.
    *   If the current index `i` falls on the direct path from `start` to `destination` (i.e., `i >= start && i < destination`), add `distance[i]` to `clockwiseDist`.
    *   Otherwise, the segment `distance[i]` belongs to the other path, so add it to `counterClockwiseDist`.
*   **Return Minimum:** After the loop completes, you will have the distances for both the clockwise and counter-clockwise paths. Return the minimum of the two.

# Solutions
### Java

```java
class Solution {
public
  int distanceBetweenBusStops(int[] distance, int start, int destination) {
    int s = Arrays.stream(distance).sum();
    int n = distance.length;
    int a = 0;
    while (start != destination) {
      a += distance[start];
      start = (start + 1) % n;
    }
    return Math.min(a, s - a);
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} distance * @param {number} start * @param {number} destination * @return {number} */ var distanceBetweenBusStops =
  function (distance, start, destination) {
    const s = distance.reduce((a, b) => a + b, 0);
    let a = 0;
    const n = distance.length;
    while (start != destination) {
      a += distance[start];
      start = (start + 1) % n;
    }
    return Math.min(a, s - a);
  };

```

### CPP

```cpp
class Solution {
public:
  int distanceBetweenBusStops(vector<int> &distance, int start,
                              int destination) {
    int s = accumulate(distance.begin(), distance.end(), 0);
    int a = 0, n = distance.size();
    while (start != destination) {
      a += distance[start];
      start = (start + 1) % n;
    }
    return min(a, s - a);
  }
};

```

### Python

```python
class Solution:
    def distanceBetweenBusStops(self, distance: List[int], start: int, destination: int) -> int: a, n = 0, len(distance) while start != destination: a += distance[start] start = (start + 1) % n return min(a, sum(distance) - a)

```