Difficulty: Easy | Acceptance: 55.30% | Paid: No Topics: Array
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.
- Examples
- Constraints
- Single Pass
- Two Pass
Examples
Example 1:
Input: distance = [1,2,3,4], start = 0, destination = 1
Output: 1
Explanation: Distance between 0 and 1 is 1 or 9, so the 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, so the minimum is 3.
Example 3:
Input: distance = [1,2,3,4], start = 0, destination = 3
Output: 4
Explanation: Distance between 0 and 3 is 4 or 6, so the minimum is 4.
Constraints
1 <= n <= 10^4
distance.length == n
0 <= start, destination < n
start != destination
0 <= distance[i] <= 10^4
Single Pass
Intuition Calculate both clockwise distance and total distance in a single loop, then find the minimum between clockwise and counter-clockwise (total - clockwise).
Steps
- Swap start and destination if start > destination to ensure we always move forward
- Iterate through the distance array once
- Accumulate total distance and clockwise distance (only between start and destination)
- Return the minimum of clockwise and counter-clockwise distances
class Solution:
def distanceBetweenBusStops(self, distance: List[int], start: int, destination: int) -> int:
if start > destination:
start, destination = destination, start
clockwise = 0
total = 0
for i in range(len(distance)):
total += distance[i]
if start <= i < destination:
clockwise += distance[i]
return min(clockwise, total - clockwise)Complexity
- Time: O(n) where n is the length of distance array
- Space: O(1)
- Notes: Single pass through the array with constant extra space
Two Pass
Intuition First calculate the total distance of the circular route, then calculate the clockwise distance between the two stops. The counter-clockwise distance is simply the difference.
Steps
- Swap start and destination if start > destination
- First pass: sum all distances to get total
- Second pass: sum distances from start to destination to get clockwise
- Return the minimum of clockwise and counter-clockwise distances
class Solution:
def distanceBetweenBusStops(self, distance: List[int], start: int, destination: int) -> int:
if start > destination:
start, destination = destination, start
total = sum(distance)
clockwise = sum(distance[start:destination])
return min(clockwise, total - clockwise)Complexity
- Time: O(n) where n is the length of distance array
- Space: O(1)
- Notes: Two passes through the array but cleaner code structure