1184. Distance Between Bus Stops
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 53.9%
Problem Breakdown
The problem involves calculating the shortest distance between two bus stops on a circular route. The input is an array distance where each element represents the distance between consecutive bus stops. The task is to find the minimum distance between two given stops, considering both clockwise and counterclockwise directions.
Inputs:
distance: An array of integers representing distances between neighboring stops.start: An integer representing the starting stop.destination: An integer representing the destination stop.
Outputs:
- The shortest distance between the start and destination stops.
Implicit Constraints/Edge Cases:
- The bus route is circular, so traveling from the last stop to the first stop is valid.
- If
startequalsdestination, the distance should be 0. - The array
distancecan have up to 10,000 elements, so the solution must be efficient in terms of time and space.
Intuition
A brute-force approach would involve calculating the total distance for both clockwise and counterclockwise routes by iterating through the array. However, this approach is inefficient with a time complexity of O(n) due to the need to traverse the entire array twice (once for each direction).
The key insight is that we can calculate the distance in one pass by determining the smaller segment between the two stops. If start is less than destination, we sum the distances from start to destination. Otherwise, we sum the distances from destination to start.
Approach
- Determine the Range: Identify the range of indices that need to be summed to calculate the distance in one direction.
- Calculate Clockwise Distance: Sum the distances between the stops in the identified range.
- Calculate Counterclockwise Distance: Subtract the clockwise distance from the total circular route distance to get the counterclockwise distance.
- Return the Minimum Distance: Compare the clockwise and counterclockwise distances and return the smaller one.
Complexity Analysis
- Time Complexity: O(n) in the worst case, where n is the length of the
distancearray. This occurs when calculating the sum for the larger segment between the two stops. - Space Complexity: O(1), as we only use a few extra variables to store distances and indices.
Solution
def distanceBetweenBusStops(distance: List[int], start: int, destination: int) -> int:
if start == destination:
return 0
# Ensure start is less than destination for easier calculation
if start > destination:
start, destination = destination, start
# Calculate the clockwise distance
clockwise_distance = sum(distance[start:destination])
# Calculate the counterclockwise distance
total_distance = sum(distance)
counterclockwise_distance = total_distance - clockwise_distance
# Return the minimum of both distances
return min(clockwise_distance, counterclockwise_distance)
Edge Cases Handled
- Same Start and Destination: If
startequalsdestination, the function returns 0 immediately. - Start Greater than Destination: The function swaps
startanddestinationto simplify the calculation of the clockwise distance. - Large Input Size: The solution efficiently handles large arrays by using a single pass to calculate distances, ensuring it remains within acceptable time limits.