Distance Between Bus Stops

Easy

#1109Time: 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.

Data structures

Array

Prompt

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:

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:

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:

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

1import java.util.*;2 3class Solution {4    public int distanceBetweenBusStops(int[] distance, int start, int destination) {5        int n = distance.length;6        if (start == destination) return 0;7 8        List<List<int[]>> adj = new ArrayList<>();9        for (int i = 0; i < n; i++) {10            adj.add(new ArrayList<>());11        }12 13        for (int i = 0; i < n; i++) {14            int u = i;15            int v = (i + 1) % n;16            int w = distance[i];17            adj.get(u).add(new int[]{v, w});18            adj.get(v).add(new int[]{u, w});19        }20 21        int[] dist = new int[n];22        Arrays.fill(dist, Integer.MAX_VALUE);23        dist[start] = 0;24 25        // Priority Queue stores {distance, node}26        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));27        pq.offer(new int[]{0, start});28 29        while (!pq.isEmpty()) {30            int[] current = pq.poll();31            int d = current[0];32            int u = current[1];33 34            if (u == destination) {35                return d;36            }37 38            if (d > dist[u]) {39                continue;40            }41 42            for (int[] edge : adj.get(u)) {43                int v = edge[0];44                int weight = edge[1];45                if (dist[u] + weight < dist[v]) {46                    dist[v] = dist[u] + weight;47                    pq.offer(new int[]{dist[v], v});48                }49            }50        }51        return -1; // Should not be reached given the problem constraints52    }53}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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:

1class Solution {2    public int distanceBetweenBusStops(int[] distance, int start, int destination) {3        // To simplify the logic, ensure start is always less than destination.4        if (start > destination) {5            int temp = start;6            start = destination;7            destination = temp;8        }9        10        int clockwiseDist = 0;11        int counterClockwiseDist = 0;12        13        for (int i = 0; i < distance.length; i++) {14            // The path from start to destination in increasing index order15            if (i >= start && i < destination) {16                clockwiseDist += distance[i];17            } else { // The other path18                counterClockwiseDist += distance[i];19            }20        }21        22        return Math.min(clockwiseDist, counterClockwiseDist);23    }24}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int distanceBetweenBusStops(int[] distance, int start, int destination) {4    int s = Arrays.stream(distance).sum();5    int n = distance.length;6    int a = 0;7    while (start != destination) {8      a += distance[start];9      start = (start + 1) % n;10    }11    return Math.min(a, s - a);12  }13}

1/** * @param {number[]} distance * @param {number} start * @param {number} destination * @return {number} */ var distanceBetweenBusStops =2  function (distance, start, destination) {3    const s = distance.reduce((a, b) => a + b, 0);4    let a = 0;5    const n = distance.length;6    while (start != destination) {7      a += distance[start];8      start = (start + 1) % n;9    }10    return Math.min(a, s - a);11  };

1class Solution {2public:3  int distanceBetweenBusStops(vector<int> &distance, int start,4                              int destination) {5    int s = accumulate(distance.begin(), distance.end(), 0);6    int a = 0, n = distance.size();7    while (start != destination) {8      a += distance[start];9      start = (start + 1) % n;10    }11    return min(a, s - a);12  }13};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem