We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Distance Between Bus Stops

Number: 1287

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given a circular route with n bus stops numbered 0 to n-1 and an array distance where distance[i] is the distance between stop i and (i+1)%n, determine the shortest distance between two given stops: start and destination. The bus travels in both clockwise and counterclockwise directions.

Key Insights

  • Recognize the circular structure of the bus stops.
  • The distance in one direction (clockwise) can be calculated by summing the distances between the two stops in order.
  • The total perimeter can be computed by summing all distances.
  • The distance in the other direction (counterclockwise) is the total distance minus the clockwise distance.
  • Return the minimum of these two distances.

Space and Time Complexity

Time Complexity: O(n), where n is the number of bus stops (we may traverse part or all of the distance array, depending on start and destination). Space Complexity: O(1) (only a few extra variables are used regardless of input size).

Solution

To solve this problem, first normalize the start and destination indices by ensuring that we always compute the clockwise distance from the smaller index to the larger index. If start is greater than destination, swap them. Next, compute the clockwise distance by summing the distances from index start to destination - 1. Then, calculate the total distance of the circular route by summing the entire array. The counterclockwise distance can be obtained by subtracting the clockwise distance from the total distance. Finally, return the smaller of the two distances. This approach leverages basic arithmetic operations and traversals, ensuring an efficient solution.

Code Solutions

# Python implementation for Distance Between Bus Stops

def distanceBetweenBusStops(distance, start, destination):
    # Ensure start is less than destination for easier calculation
    if start > destination:
        start, destination = destination, start

    # Calculate the clockwise distance from start to destination
    clockwise_distance = sum(distance[start:destination])
    
    # Calculate the total distance around the circle
    total_distance = sum(distance)
    
    # The counterclockwise distance is the total minus the clockwise distance
    counterclockwise_distance = total_distance - clockwise_distance
    
    # Return the minimum of the two possible distances
    return min(clockwise_distance, counterclockwise_distance)

# Example usage:
# distance = [1,2,3,4]
# print(distanceBetweenBusStops(distance, 0, 1))  # Output: 1
← Back to All Questions