Distance Between Bus Stops
EasyPrompt
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^4distance.length == n0 <= start, destination < n0 <= 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 vertexiand vertex(i + 1) % nwith the weight beingdistance[i]. - Initialization: Create a distance array,
dist, of sizenand initialize all values to infinity, except for thestartvertex, 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
uwith the smallest distance. - Relax Edges: For each neighbor
vofu, if the path throughuis shorter than the known distance tov(i.e.,dist[u] + weight(u, v) < dist[v]), updatedist[v]and add the new pair(dist[v], v)to the priority queue. - Termination: The algorithm can terminate as soon as the
destinationvertex 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) % nand vice-versa, with the weightdistance[i]. - Initialization: We use a distance array
distto store the shortest distance fromstartto 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 neighborsvand updates their distances if a shorter path is found viau. This process is called edge relaxation. - Result: Once the
destinationstop is reached and extracted from the priority queue, its distance is guaranteed to be the shortest possible from thestartstop.
Here is a Java implementation of this approach:
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 }}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.
Solutions
Solution
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); }}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.