How do you solve Distance Between Bus Stops on LeetCode?

Distance Between Bus Stops (LeetCode #1184) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Understanding the circular nature of the bus stops is crucial for calculating distances efficiently.

What is the brute force solution for Distance Between Bus Stops?

The brute force approach for Distance Between Bus Stops is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach calculates the distance between the start and destination by checking both clockwise and counterclockwise paths. This method is straightforward but inefficient for larger inputs. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Distance Between Bus Stops?

Distance Between Bus Stops uses the following concepts: Array. The recommended patterns to study are: Array, Prefix Sum.

What are the interview tips for Distance Between Bus Stops?

Always clarify the problem statement and constraints before diving into coding. Consider edge cases, such as when start and destination are the same. Explain your thought process while coding; it shows your understanding and helps the interviewer follow along.

What are common mistakes when solving Distance Between Bus Stops?

Confusing the order of start and destination, which can lead to incorrect distance calculations. Not considering the circular nature of the bus stops, leading to missing distances.

#1184

Distance Between Bus Stops

Easy

ArrayArrayPrefix Sum

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution calculates the distances in a single pass, making it more efficient. By leveraging the circular nature of the bus stops, we can compute both distances directly.

⚙️

Algorithm

5 steps

1Step 1: Ensure start is less than destination for easier calculations.
2Step 2: Calculate the clockwise distance by summing the distances from start to destination.
3Step 3: Calculate the total distance of the entire route.
4Step 4: Calculate the counterclockwise distance as the total distance minus the clockwise distance.
5Step 5: Return the minimum of the clockwise and counterclockwise distances.

solution.py9 lines

1# Full working Python code
2
3def distance_between_bus_stops(distance, start, destination):
4    if start > destination:
5        start, destination = destination, start
6    clockwise_distance = sum(distance[start:destination])
7    total_distance = sum(distance)
8    counterclockwise_distance = total_distance - clockwise_distance
9    return min(clockwise_distance, counterclockwise_distance)

ℹ

Complexity note: The time complexity is O(n) because we only traverse the distance array a couple of times, making it linear with respect to the number of stops.

1Understanding the circular nature of the bus stops is crucial for calculating distances efficiently.
2Recognizing that both clockwise and counterclockwise paths need to be considered helps in finding the shortest distance.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.