Leetcode – Distance Between Bus Stops Solution

Spread the love

The “Distance Between Bus Stops” is a classical problem on Leetcode that belongs to the array category. The problem tests the fundamentals of array manipulation and mathematical reasoning. In this article, we will discuss different approaches to solve this problem, covering their time and space complexities. By the end, you’ll have a comprehensive understanding of how to solve problems related to circular arrays and distance calculations.

Problem Statement

Before diving into the solution, let’s first understand the problem itself.

Problem Description

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 numbered i and i+1 in the array. You are standing at stop 0. The bus goes to stop n-1 and then goes back to stop 0. In other words, the bus moves in a circle.

The task is to return the shortest distance between stops start and destination. You can assume that at most one bus is operating on the circuit. You may choose to travel in either direction around the circle.

Constraints

  • 1 <= n <= 10^4
  • distance.length == n
  • 1 <= distance[i] <= 10^4
  • 0 <= start, destination < n

Understanding the Problem

The problem can be thought of as a circular array traversal problem where we can go either clockwise or counter-clockwise. We need to find the shorter distance between the start and destination stops.

Approaches

Brute-Force Approach

One naive way to solve this problem is to compute both distances (clockwise and counter-clockwise) between the start and destination stops, and then return the shorter one.

Algorithm

  1. Initialize two variables clockwise_distance and counter_clockwise_distance to zero.
  2. Traverse the array from the start index to the destination index in a clockwise manner, summing up distances along the way and store it in clockwise_distance.
  3. Traverse the array from the start index to the destination index in a counter-clockwise manner, summing up distances along the way and store it in counter_clockwise_distance.
  4. Return the minimum between clockwise_distance and counter_clockwise_distance.

Python Code Implementation

def distance_between_bus_stops(distance, start, destination):
    n = len(distance)
    clockwise_distance = 0
    counter_clockwise_distance = 0

    # Calculate the clockwise distance
    i = start
    while i != destination:
        clockwise_distance += distance[i]
        i = (i + 1) % n

    # Calculate the counter-clockwise distance
    i = start
    while i != destination:
        i = (i - 1 + n) % n
        counter_clockwise_distance += distance[i]

    return min(clockwise_distance, counter_clockwise_distance)

Time Complexity

The time complexity for this approach is O(n).

Space Complexity

The space complexity for this approach is O(1).

Optimized Approach

We can further optimize our solution. One key observation is that once we calculate the clockwise distance, the counter-clockwise distance is simply the total distance minus the clockwise distance.

Algorithm

  1. Initialize clockwise_distance to zero.
  2. Traverse the array from the start index to the destination index in a clockwise manner, summing up distances along the way and store it in clockwise_distance.
  3. Calculate total_distance by summing up all the elements in the distance array.
  4. Calculate counter_clockwise_distance by subtracting clockwise_distance from total_distance.
  5. Return the minimum between clockwise_distance and counter_clockwise_distance.

Python Code Implementation

def distance_between_bus_stops(distance, start, destination):
    n = len(distance)
    clockwise_distance = 0
    total_distance = sum(distance)

    i = start
    while i != destination:
        clockwise_distance += distance[i]
        i = (i + 1) % n

    counter_clockwise_distance = total_distance - clockwise_distance

    return min(clockwise_distance, counter_clockwise_distance)

Time Complexity

The time complexity for this approach is O(n).

Space Complexity

The space complexity for this approach is O(1).

Conclusion

The “Distance Between Bus Stops” problem is a classic example of circular array manipulation. While a brute-force approach works well within the constraints, an optimized approach offers a slightly more elegant solution without any real gain in efficiency for this problem’s constraints. Both approaches give us O(n) time complexity and O(1) space complexity.

Leave a Reply