#1184

Easy

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Distance Between Bus Stops

Compute the minimal distance between two bus stops on a circular route using an array-driven solution approach.

Problem Statement

You are given a circular route with n bus stops labeled from 0 to n-1. An array distance of length n provides the distance between each consecutive stop where distance[i] represents the distance from stop i to stop (i + 1) % n. The bus can travel in both clockwise and counterclockwise directions along this circular route.

Given two integers start and destination representing bus stops, return the minimum distance between them. You must account for traveling in both directions, efficiently summing distances and considering circular array wraparound to determine the shortest path.

Examples

Example 1

Input: distance = [1,2,3,4], start = 0, destination = 1

Output: 1

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

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

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

Solution Approach

Calculate Clockwise Distance

Traverse the distance array from start to destination in the forward direction, summing distances. Use modulo n to handle circular wraparound to avoid index out-of-bound errors.

Calculate Counterclockwise Distance

Sum distances in the opposite direction by traversing from destination back to start. This can be derived by subtracting the clockwise distance from the total sum of the array, ensuring an O(n) approach without repeated iteration.

Return the Minimum Distance

Compare the clockwise and counterclockwise totals and return the smaller value. This ensures the result always reflects the shortest path on the circular route.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) as we may traverse the array once to compute total distance and again for clockwise sum. Space complexity is O(1) since no additional arrays or structures are required beyond variables to track sums.

What Interviewers Usually Probe

Checks if you handle circular array indices correctly.
Wants an efficient solution that avoids double-counting distances.
Looks for correct computation of both clockwise and counterclockwise paths.

Common Pitfalls or Variants

Common pitfalls

Ignoring circular wraparound and causing index out-of-range errors.
Summing only one direction and missing the shorter counter-direction path.
Confusing start and destination indices, leading to incorrect distance calculations.

Follow-up variants

Compute distances for multiple pairs of stops efficiently using prefix sums.
Modify distances dynamically and query shortest paths repeatedly.
Handle weighted circular routes where distances change over time.

FAQ

How do I handle the circular nature of the bus route in this problem?

Use modulo n when accessing array indices to wrap around from the last stop back to the first stop.

Can I just sum distances from start to destination in one direction?

No, because the counterclockwise path may be shorter; always compare both directions to find the minimum.

What is the time complexity of the optimal solution?

O(n) time complexity since you may need to traverse the distance array to calculate total distance and directional sums.

Does the distance array ever contain negative numbers?

No, all distance[i] values are non-negative, so summing them gives valid path lengths.

What pattern does this problem follow in algorithm interviews?

It follows the array-driven solution strategy pattern where careful index handling and cumulative sums determine optimal paths.

terminal

Solution

Solution 1: Simulation

We can first calculate the total distance $s$ that the bus travels, then simulate the bus's journey. Starting from the departure point, we move one stop to the right each time until we reach the destination, recording the travel distance $t$ during this process. Finally, we return the minimum value between $t$ and $s - t$.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def distanceBetweenBusStops(
        self, distance: List[int], start: int, destination: int
    ) -> int:
        s = sum(distance)
        t, n = 0, len(distance)
        while start != destination:
            t += distance[start]
            start = (start + 1) % n
        return min(t, s - t)

Continue Practicing

#1186 maximum subarray sum with one deletion #1187 make array strictly increasing #1178 number of valid words for each puzzle