1184. Distance Between Bus Stops
Problem Description
The problem presents a circular bus route consisting of n
stops, numbered from 0
to n - 1
. Each stop is connected to the next, and the last stop is connected back to the first, forming a circle. The array distance
contains the distances between each pair of consecutive stops (i
and (i + 1) % n
). The bus can travel in both the clockwise and counterclockwise directions.
The task is to calculate the shortest distance between two given stops: the start
and the destination
. Since the bus can travel in both directions, we need to compare the travel distances and choose the one that requires the least amount of travel.
Intuition
The solution is based on the premise that the shortest distance between two points in a circle can be in either the clockwise or counter-clockwise direction. Therefore, we need to:
- Calculate the distance traveling from
start
todestination
clockwise. - Calculate the total distance around the circle to find the distance of the counter-clockwise path, which is the total distance minus the clockwise distance.
- Finally, return the smaller of the two calculated distances.
To achieve this, an intuitive approach is to:
- Iterate from the
start
stop to thedestination
stop, accumulating the distances between consecutive stops. - Then, calculate the sum of all distances to capture the complete circuit distance.
- The clockwise distance is the accumulation from start to
destination
. - The counterclockwise distance can be derived by subtracting the clockwise distance from the total distance.
- After having both distances, we compare them and return the smaller one as the shortest path between the
start
anddestination
stops.
Solution Approach
The implementation of the solution follows these steps:
-
Initializing Accumulator (
a
) and Circle Size (n
): An accumulator variablea
is set to 0 to keep track of the distance traveled in the clockwise direction. The variablen
denotes the size of the distance array, which is equivalent to the number of stops in the circle. -
Iterative Computation of Clockwise Distance: A while loop is used to traverse the bus stops from
start
todestination
. During each iteration, the distance from the current stop to the next is added to the accumulatora
. The current stopstart
is updated to the next stop using(start + 1) % n
. This update statement guarantees that the index remains within the bounds of the array, effectively looping from the last stop back to the first. The loop continues untilstart
matchesdestination
. -
Calculation of Counterclockwise Distance: Once the clockwise distance is known, the counterclockwise distance is calculated by subtracting the accumulator
a
from the sum of all distances in the array. The built-insum()
function computes the total circle distance. -
Return Minimum Distance: Using the built-in
min()
function, the algorithm then returns the smaller value between the accumulated clockwise distancea
and the counterclockwise distance (sum(distance) - a
).
This approach uses no complex data structures; it relies on arithmetic and looping to achieve the desired outcome. The pattern involves traversing the array in a circular fashion using modulo arithmetic, which is a common technique in problems involving circular data structures. Additionally, the use of built-in functions for summing and finding the minimum value makes the code concise and efficient.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a simple example:
Suppose we have 5 bus stops on a circular route with the following distances between consecutive stops: distance = [3, 10, 1, 5, 8]
. Thus, we have n = 5
(5 stops).
- The distance from stop 0 to stop 1 is 3.
- The distance from stop 1 to stop 2 is 10.
- The distance from stop 2 to stop 3 is 1.
- The distance from stop 3 to stop 4 is 5.
- The distance from stop 4 back to stop 0 is 8.
Now, let's find the shortest distance between start = 1
and destination = 3
.
Following the solution approach:
-
Initializing Accumulator (
a
) and Circle Size (n
):- Set
a = 0
n
equals the length of the distance array, son = 5
.
- Set
-
Iterative Computation of Clockwise Distance:
- Start at
start = 1
. Add toa
the distance to the next stop (distance[1] = 10). - Move to the next stop,
start = (1 + 1) % 5 = 2
. Add toa
the distance to the next stop (distance[2] = 1). - Since we've reached the
destination
stop, we stop accumulating the distance. The clockwise distancea
is now10 + 1 = 11
.
- Start at
-
Calculation of Counterclockwise Distance:
- Compute the sum of all distances:
sum(distance) = 3 + 10 + 1 + 5 + 8 = 27
. - Calculate the counterclockwise distance:
27 - 11 = 16
.
- Compute the sum of all distances:
-
Return Minimum Distance:
- Compare the clockwise and counterclockwise distances and choose the smaller one.
- Since
11 < 16
, the shortest distance is11
.
Hence, for this example, the shortest distance from stop 1 to stop 3 is 11
units.
Solution Implementation
1class Solution:
2 def distanceBetweenBusStops(self, distances: List[int], start: int, destination: int) -> int:
3 # Initialize the distance traveled clockwise from 'start' to 'destination'
4 clockwise_distance = 0
5 # Total number of bus stops
6 total_stops = len(distances)
7
8 # Adjust indices if 'start' is greater than 'destination' for a direct path
9 if start > destination:
10 start, destination = destination, start
11
12 # Calculate the clockwise distance by adding the distances of each stop
13 for i in range(start, destination):
14 clockwise_distance += distances[i]
15
16 # Calculate the counter-clockwise distance by subtracting the clockwise distance
17 # from the total distance around the bus stops
18 counter_clockwise_distance = sum(distances) - clockwise_distance
19
20 # Return the minimum of the two distances as the result
21 return min(clockwise_distance, counter_clockwise_distance)
22
23# Note: It is important to import List from typing to use the List type hint in the function signature.
24from typing import List
25
1class Solution {
2 public int distanceBetweenBusStops(int[] distances, int start, int destination) {
3 // Calculate the total distance of the circular route.
4 int totalDistance = 0;
5 for (int distance : distances) {
6 totalDistance += distance;
7 }
8
9 // Initialize the clock-wise distance traveled.
10 int clockwiseDistance = 0;
11
12 // Calculate the clock-wise distance from 'start' to 'destination'.
13 int currentIndex = start;
14 while (currentIndex != destination) {
15 clockwiseDistance += distances[currentIndex];
16 currentIndex = (currentIndex + 1) % distances.length; // Move to the next stop in a circular manner.
17 }
18
19 // Calculate the counter-clockwise distance by subtracting the
20 // clock-wise distance from the total distance.
21 int counterClockwiseDistance = totalDistance - clockwiseDistance;
22
23 // Return the minimum of the clock-wise and counter-clockwise distances.
24 return Math.min(clockwiseDistance, counterClockwiseDistance);
25 }
26}
27
1#include <vector>
2#include <numeric>
3
4class Solution {
5public:
6 int distanceBetweenBusStops(std::vector<int>& distance, int start, int destination) {
7 // Calculate the sum of all distances
8 int totalDistance = std::accumulate(distance.begin(), distance.end(), 0);
9
10 // Initialize the distance for the first path
11 int pathDistance = 0;
12
13 // Calculate the length of the bus route
14 int numStops = distance.size();
15
16 // Add up distances in the clockwise direction from start to destination
17 while (start != destination) {
18 pathDistance += distance[start];
19
20 // Wrap around if we reach the end of the vector
21 start = (start + 1) % numStops;
22 }
23
24 // Return the minimum of the clockwise distance and the counterclockwise distance
25 // since buses can travel in both directions
26 return std::min(pathDistance, totalDistance - pathDistance);
27 }
28};
29
1// Calculates the shortest distance between two bus stops on a circular route
2// distance: array representing the distances between each pair of adjacent bus stops
3// start: the start bus stop index
4// destination: the destination bus stop index
5function distanceBetweenBusStops(distance: number[], start: number, destination: number): number {
6 // Calculate the total distance of the entire circular route
7 const totalDistance = distance.reduce((accumulatedDistance, currentDistance) => accumulatedDistance + currentDistance, 0);
8
9 // Calculate the distance of the path from 'start' to 'destination' moving forward
10 let distanceForward = 0;
11 const numOfStops = distance.length;
12
13 // Loop through the bus stops from 'start' to 'destination'
14 while (start !== destination) {
15 // Accumulate the distance of the direct path
16 distanceForward += distance[start];
17 // Move to the next stop, wrap around to 0 if at the end of the array
18 start = (start + 1) % numOfStops;
19 }
20
21 // Return the minimum between the direct path and the reverse path
22 // The reverse path is the total distance minus the direct path distance
23 return Math.min(distanceForward, totalDistance - distanceForward);
24}
25
Time and Space Complexity
The time complexity of the code is O(n)
where n
is the number of elements in the distance
list. This results from iterating over the elements starting from the start
index and stopping once it reaches the destination
. In the worst case, this could require traversing the entire list.
The space complexity of the code is O(1)
since it uses a fixed amount of additional space. The variables a
, n
, and start
are the only extra storage used and do not depend on the size of the input list.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following problems can be solved with backtracking (select multiple)
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!