Problem Description

You have a circular bus route with n stops numbered from 0 to n - 1. These stops form a circle, meaning after stop n - 1, the bus returns to stop 0.

You're given an array distance where distance[i] represents the distance between stop i and stop (i + 1) % n. The modulo operation ensures that after the last stop, we wrap around to the first stop.

The bus can travel in two directions:

• Clockwise: from stop i to stop (i + 1) % n
• Counterclockwise: from stop i to stop (i - 1 + n) % n

Given a start stop and a destination stop, you need to find the shortest distance the bus needs to travel to get from the start to the destination.

For example, if you have 4 stops with distances [1, 2, 3, 4]:

• Distance from stop 0 to stop 1 is 1
• Distance from stop 1 to stop 2 is 2
• Distance from stop 2 to stop 3 is 3
• Distance from stop 3 to stop 0 is 4

To travel from stop 0 to stop 2, you could go:

• Clockwise: 0 → 1 → 2 with total distance = 1 + 2 = 3
• Counterclockwise: 0 → 3 → 2 with total distance = 4 + 3 = 7

The shortest distance would be 3.

The solution calculates the total distance s of the entire circle, then simulates traveling clockwise from start to destination to get distance t. The minimum between t (clockwise distance) and s - t (counterclockwise distance) gives the shortest path.

Intuition

Since the bus stops form a circle, there are exactly two paths between any two stops - going clockwise or going counterclockwise. The key insight is that these two paths together make up the entire circle.

Think of it like this: if you're standing at point A on a circle and want to reach point B, you can either go around the circle in one direction or the opposite direction. Whatever distance you don't travel in one direction is exactly the distance you would travel in the other direction.

This means if the total distance around the entire circle is s, and the clockwise distance from start to destination is t, then the counterclockwise distance must be s - t. This is because the clockwise path plus the counterclockwise path equals the complete circle.

For example, imagine a circular track that's 10 units around. If going clockwise from A to B takes 3 units, then going counterclockwise must take 10 - 3 = 7 units. There's no need to simulate both directions separately.

Therefore, our approach is:

1. Calculate the total distance s by summing all distances in the array
2. Simulate only the clockwise journey from start to destination to find distance t
3. The counterclockwise distance is automatically s - t
4. Return min(t, s - t) to get the shorter path

This elegant solution leverages the circular property of the problem - we only need to calculate one direction, and the other direction's distance comes for free through simple subtraction.

Solution Approach

The implementation follows a straightforward simulation approach:

1. Calculate Total Distance: First, we compute the sum of all distances in the array using s = sum(distance). This gives us the total distance around the entire circular route.

2. Initialize Variables: We set t = 0 to track the clockwise distance from start to destination, and n = len(distance) to store the number of stops.

3. Simulate Clockwise Travel: We use a while loop that continues until start equals destination:

   • Add the current distance distance[start] to our running total t
   • Move to the next stop using start = (start + 1) % n
   • The modulo operation ensures we wrap around to stop 0 after reaching the last stop

4. Return Minimum Distance: Finally, we return min(t, s - t) where:

   • t is the clockwise distance we calculated
   • s - t is the counterclockwise distance (total minus clockwise)

The algorithm has a time complexity of O(n) where n is the number of stops, as we might need to traverse all stops in the worst case. The space complexity is O(1) since we only use a constant amount of extra space.

The beauty of this solution lies in its simplicity - by recognizing that clockwise + counterclockwise = total distance, we only need to calculate one direction and derive the other through subtraction. This eliminates the need for two separate simulations or complex path-finding algorithms.

Example Walkthrough

Let's walk through a concrete example with 5 bus stops and the following distances:

• distance = [7, 10, 1, 12, 11]
• start = 1
• destination = 3

This means:

• Stop 0 to Stop 1: distance 7
• Stop 1 to Stop 2: distance 10
• Stop 2 to Stop 3: distance 1
• Stop 3 to Stop 4: distance 12
• Stop 4 to Stop 0: distance 11

Step 1: Calculate Total Distance

s = sum([7, 10, 1, 12, 11]) = 41

The entire circular route is 41 units long.

Step 2: Initialize Variables

t = 0 (clockwise distance tracker)
n = 5 (number of stops)
current_position = start = 1

Step 3: Simulate Clockwise Travel from Stop 1 to Stop 3

Iteration 1:

• Currently at stop 1, need to reach stop 3
• Add distance from stop 1 to stop 2: t = 0 + distance[1] = 0 + 10 = 10
• Move to next stop: current_position = (1 + 1) % 5 = 2

Iteration 2:

• Currently at stop 2, need to reach stop 3
• Add distance from stop 2 to stop 3: t = 10 + distance[2] = 10 + 1 = 11
• Move to next stop: current_position = (2 + 1) % 5 = 3

Loop ends as current_position equals destination

Step 4: Calculate Both Distances and Return Minimum

• Clockwise distance: t = 11
• Counterclockwise distance: s - t = 41 - 11 = 30
• Return: min(11, 30) = 11

The shortest path from stop 1 to stop 3 is going clockwise with a total distance of 11 units (10 + 1), rather than going counterclockwise which would require traveling 30 units (11 + 12 + 7).

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array distance. This is because:

• Computing the sum of all distances takes O(n) time
• The while loop iterates from start to destination in the circular array, which in the worst case visits all n elements (when we need to go almost the full circle)
• Each operation inside the loop takes O(1) time

The space complexity is O(1). The algorithm only uses a constant amount of extra space:

• Variables s (sum), t (accumulated distance), and n (length) each require O(1) space
• No additional data structures are created that depend on the input size

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling the Case When Start > Destination

A common mistake is assuming that we always travel from a lower-numbered stop to a higher-numbered stop. When start > destination, the clockwise path will wrap around through stop 0, which the modulo operation handles correctly. However, some might try to "optimize" by swapping start and destination, which would give incorrect results since the distances are directional.

Incorrect Approach:

# Wrong: This changes the direction of travel
if start > destination:
    start, destination = destination, start

Why it's wrong: The distance array is directional. distance[i] specifically represents the distance from stop i to stop (i+1)%n, not the reverse. Swapping start and destination would calculate a different path entirely.

2. Off-by-One Error in Loop Termination

Another pitfall is including the distance from the destination stop in the calculation:

Incorrect Code:

while current_stop <= destination:  # Wrong condition
    clockwise_distance += distance[current_stop]
    current_stop = (current_stop + 1) % n

Why it's wrong: This would add distance[destination] to the total, which represents the distance from the destination to the next stop - distance we don't actually travel.

3. Integer Overflow in Other Languages

While not an issue in Python, developers translating this solution to languages like C++ or Java might face integer overflow when summing large distance values.

Solution: Use appropriate data types (like long long in C++ or long in Java) when calculating the total distance.

4. Assuming Direct Index-Based Calculation

Some might try to avoid the loop entirely with:

Incorrect Approach:

# Wrong: Doesn't handle wrap-around
clockwise_distance = sum(distance[start:destination])

Why it's wrong: This fails when start > destination because the slice would be empty or incorrect. The circular nature requires us to potentially sum distances that wrap around from the end of the array back to the beginning.

Correct Alternative (if you want to avoid simulation):

if start <= destination:
    clockwise_distance = sum(distance[start:destination])
else:
    clockwise_distance = sum(distance[start:]) + sum(distance[:destination])

This handles both cases correctly but requires more conditional logic.