Jobs

Interviews

Discussions

Distance Between Bus Stops

Easy

Asked by:

11 views

Topics:

Arrays

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^4
distance.length == n
0 <= start, destination < n
0 <= distance[i] <= 10^4

Try coding it in LeetCode

Distance Between Bus Stops

Easy

Asked by:

11 views

Topics:

Arrays

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^4
distance.length == n
0 <= start, destination < n
0 <= distance[i] <= 10^4

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the distances between bus stops in the array?
Can the start and destination locations be the same? If so, what should the function return?
Is the destination guaranteed to be reachable from the start, or should I handle the case where it's not?
Are the start and destination indices guaranteed to be within the bounds of the distances array?
Are the distances in the array integers, or can they be floating-point numbers?

Brute Force Solution

Approach

The brute force approach involves checking every possible route between the start and destination bus stops. We will calculate the distance for each possible path and select the shortest one. This guarantees finding the optimal answer but can be inefficient.

Here's how the algorithm would work step-by-step:

First, consider the distance traveling in the clockwise direction around the bus route.
Next, calculate the distance traveling in the counter-clockwise direction around the bus route.
Compare the clockwise and counter-clockwise distances.
Finally, select the shorter of the two distances as the answer.

Code Implementation

def distance_between_bus_stops_brute_force(distances, start, destination):
    total_distance = sum(distances)

    # Calculate clockwise distance.
    clockwise_distance = 0
    current_index = start
    while current_index != destination:

        clockwise_distance += distances[current_index]
        current_index = (current_index + 1) % len(distances)

    # Calculate counter-clockwise distance. 
    counterclockwise_distance = total_distance - clockwise_distance

    # Compare the two distances and return the minimum.
    if clockwise_distance < counterclockwise_distance:
        return clockwise_distance
    else:
        return counterclockwise_distance

Big(O) Analysis

Time Complexity

O(n) – The algorithm calculates the clockwise and counter-clockwise distances between the start and destination bus stops. Calculating the clockwise distance involves iterating through a portion of the distances array in the clockwise direction which is bounded by the size of the array, n. Similarly, the counter-clockwise calculation iterates through a portion of the array, also bounded by n. Since we perform these two calculations independently and then compare the results, the dominant factor is the single pass through at most all the elements of the array, leading to O(n) time complexity.

Space Complexity

O(1) – The algorithm calculates two distances, clockwise and counter-clockwise, and stores them in variables. It then compares these two distances. The space required for these variables is constant and does not depend on the number of bus stops, N. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

To find the shortest distance between two bus stops on a circular route, we can consider the distance in both directions. We can calculate the distance in one direction and then simply subtract that value from the total route length to get the distance in the other direction and see which one is smaller.

Here's how the algorithm would work step-by-step:

First, figure out which stop is the starting point and which is the ending point based on their order around the circle.
Calculate the total distance by going forward around the circle from the start to the end.
Calculate the total distance of the entire circular route.
Now, subtract the forward distance from the total distance of the whole route. This will give you the distance going backward around the circle.
Compare the forward distance and the backward distance. Pick the shorter distance between the two.

Code Implementation

def distance_between_bus_stops(distances, start_stop, destination_stop):
    number_of_stops = len(distances)

    # Determine forward direction
    if start_stop > destination_stop:
        start_stop, destination_stop = destination_stop, start_stop

    forward_distance = 0
    for i in range(start_stop, destination_stop):
        forward_distance += distances[i]

    # Calculate total distance of the circle
    total_distance = sum(distances)

    # Find the distance in the reverse direction
    backward_distance = total_distance - forward_distance

    # Return the shortest distance.
    return min(forward_distance, backward_distance)

Big(O) Analysis

Time Complexity

O(n) – The algorithm calculates the distance between two bus stops on a circular route. Finding the total distance from the start to the destination iterates through a portion of the input array distances, which in the worst case is the entire array of size n. Calculating the total distance of the entire route also iterates through the entire array of size n. Other operations are constant time operations. Therefore, the dominant factor is iterating through the array once or twice, resulting in O(n) time complexity.

Space Complexity

O(1) – The algorithm calculates distances and stores them in a few scalar variables (forward distance, total distance, backward distance). These variables consume a constant amount of space irrespective of the number of bus stops (N). Therefore, the auxiliary space used by this algorithm is constant, resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Empty distance array	Return 0 immediately as there are no distances to traverse.
Start and destination are the same	Return 0 immediately as the distance between the same location is zero.
Array with only one distance value	Return the distance itself if start is 0 and destination is 1; otherwise return 0.
Start index is greater than the length of the distance array	Use modulo operator (%) to wrap the index around to the beginning of the array.
Destination index is greater than the length of the distance array	Use modulo operator (%) to wrap the index around to the beginning of the array.
Negative distances in the array	Take the absolute value of distances before summing them to ensure non-negative distances.
Integer overflow when calculating the total distance	Use a larger data type (e.g., long) to store the total distance to prevent overflow.
Start index is greater than the destination index.	Calculate both clockwise and counterclockwise distances, then return the minimum of the two.

Empty distance array

How to Handle:

Return 0 immediately as there are no distances to traverse.

Start and destination are the same

How to Handle:

Return 0 immediately as the distance between the same location is zero.

Array with only one distance value

How to Handle:

Return the distance itself if start is 0 and destination is 1; otherwise return 0.

Start index is greater than the length of the distance array

How to Handle:

Use modulo operator (%) to wrap the index around to the beginning of the array.

Destination index is greater than the length of the distance array

How to Handle:

Use modulo operator (%) to wrap the index around to the beginning of the array.

Negative distances in the array

How to Handle:

Take the absolute value of distances before summing them to ensure non-negative distances.

Integer overflow when calculating the total distance

How to Handle:

Use a larger data type (e.g., long) to store the total distance to prevent overflow.

Start index is greater than the destination index.

How to Handle:

Calculate both clockwise and counterclockwise distances, then return the minimum of the two.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the distances between bus stops in the array?
Can the start and destination locations be the same? If so, what should the function return?
Is the destination guaranteed to be reachable from the start, or should I handle the case where it's not?
Are the start and destination indices guaranteed to be within the bounds of the distances array?
Are the distances in the array integers, or can they be floating-point numbers?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, consider the distance traveling in the clockwise direction around the bus route.
Next, calculate the distance traveling in the counter-clockwise direction around the bus route.
Compare the clockwise and counter-clockwise distances.
Finally, select the shorter of the two distances as the answer.

Code Implementation

def distance_between_bus_stops_brute_force(distances, start, destination):
    total_distance = sum(distances)

    # Calculate clockwise distance.
    clockwise_distance = 0
    current_index = start
    while current_index != destination:

        clockwise_distance += distances[current_index]
        current_index = (current_index + 1) % len(distances)

    # Calculate counter-clockwise distance. 
    counterclockwise_distance = total_distance - clockwise_distance

    # Compare the two distances and return the minimum.
    if clockwise_distance < counterclockwise_distance:
        return clockwise_distance
    else:
        return counterclockwise_distance

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, figure out which stop is the starting point and which is the ending point based on their order around the circle.
Calculate the total distance by going forward around the circle from the start to the end.
Calculate the total distance of the entire circular route.
Now, subtract the forward distance from the total distance of the whole route. This will give you the distance going backward around the circle.
Compare the forward distance and the backward distance. Pick the shorter distance between the two.

Code Implementation

def distance_between_bus_stops(distances, start_stop, destination_stop):
    number_of_stops = len(distances)

    # Determine forward direction
    if start_stop > destination_stop:
        start_stop, destination_stop = destination_stop, start_stop

    forward_distance = 0
    for i in range(start_stop, destination_stop):
        forward_distance += distances[i]

    # Calculate total distance of the circle
    total_distance = sum(distances)

    # Find the distance in the reverse direction
    backward_distance = total_distance - forward_distance

    # Return the shortest distance.
    return min(forward_distance, backward_distance)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty distance array	Return 0 immediately as there are no distances to traverse.
Start and destination are the same	Return 0 immediately as the distance between the same location is zero.
Array with only one distance value	Return the distance itself if start is 0 and destination is 1; otherwise return 0.
Start index is greater than the length of the distance array	Use modulo operator (%) to wrap the index around to the beginning of the array.
Destination index is greater than the length of the distance array	Use modulo operator (%) to wrap the index around to the beginning of the array.
Negative distances in the array	Take the absolute value of distances before summing them to ensure non-negative distances.
Integer overflow when calculating the total distance	Use a larger data type (e.g., long) to store the total distance to prevent overflow.
Start index is greater than the destination index.	Calculate both clockwise and counterclockwise distances, then return the minimum of the two.

Empty distance array

How to Handle:

Return 0 immediately as there are no distances to traverse.

Start and destination are the same

How to Handle:

Return 0 immediately as the distance between the same location is zero.

Array with only one distance value

How to Handle:

Return the distance itself if start is 0 and destination is 1; otherwise return 0.

Start index is greater than the length of the distance array

How to Handle:

Use modulo operator (%) to wrap the index around to the beginning of the array.

Destination index is greater than the length of the distance array

How to Handle:

Use modulo operator (%) to wrap the index around to the beginning of the array.

Negative distances in the array

How to Handle:

Take the absolute value of distances before summing them to ensure non-negative distances.

Integer overflow when calculating the total distance

How to Handle:

Use a larger data type (e.g., long) to store the total distance to prevent overflow.

Start index is greater than the destination index.

How to Handle:

Calculate both clockwise and counterclockwise distances, then return the minimum of the two.