Python 1184.py
class Solution:
def distanceBetweenBusStops(self, distance: List[int], start: int, destination: int) -> int:
total = sum(distance)
drive = 0
for i in range(min(start, destination), max(start, destination)):
drive += distance[i]
return min(drive, total - drive)
Difficulty
and has an acceptance rate of about 56% (100k+ submissions).
Typical patterns to solve this problem:
- Array
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation solves the classic circular bus-route problem: given an array of distances between consecutive bus stops, a starting stop, and a destination stop, it returns the shortest travel distance either clockwise or counter-clockwise. The algorithm first computes the total perimeter of the circular route, then accumulates the distance along the direct segment between the two stops, and finally selects the smaller of the two possible travel distances.
Key Steps
The first logical step is to determine the total length of the circular route. This is achieved with a single call to the built-in sum function, which iterates over the distance list once.
total = sum(distance)
Next, the code prepares a variable to hold the distance traveled along the direct segment between the two stops. The variable drive is initialized to zero.
drive = 0
The core of the algorithm is a loop that iterates from the lower index of the two stops to the higher index, adding each segment length to drive. By using min(start, destination) and max(start, destination), the loop works correctly regardless of the order in which start and destination are supplied.
for i in range(min(start, destination), max(start, destination)):
drive += distance[i]
Finally, the function returns the minimum between the accumulated direct distance and the complementary distance obtained by subtracting drive from the total perimeter. This choice yields the shortest possible travel distance on the circular route.
return min(drive, total - drive)
Edge Cases Handled
When start and destination refer to the same stop, the range in the loop becomes empty because the lower and upper bounds are equal. Consequently, drive remains zero, and the function correctly returns zero as the shortest distance.
If start is greater than destination, the use of min and max ensures that the loop still traverses the correct segment in the forward direction of the array, effectively handling the wrap-around scenario without additional conditional logic.
When the distance list contains a single element, representing a route with only one segment, the total sum equals that element, and the loop either adds that element (if the two stops differ) or adds nothing (if they are the same). The final min operation then yields the correct shortest distance, demonstrating robustness for minimal input sizes.
Performance Optimizations
The algorithm leverages Python’s built-in sum function, which is implemented in C and provides a fast aggregation of the list elements. By computing the total perimeter once, the code avoids repeated summations that could arise from recomputing the complementary distance inside a loop.
The loop iterates only over the segment between the two stops, rather than traversing the entire list. This selective iteration reduces the number of additions performed, especially when the two stops are close together on the circle. The use of range(min(...), max(...)) eliminates the need for conditional branching inside the loop, allowing the interpreter to execute a straightforward sequence of additions.
The final min call is a constant-time operation that selects the smaller of the two pre-computed distances, completing the computation with minimal overhead. Overall, the solution achieves linear time proportional to the number of segments traversed in the direct path, while keeping auxiliary memory usage to a constant amount.
ELI5 - Simplified Explanation
Imagine there is a round bus route that stops at different places in a circle. Each number in the little list tells you how long the ride lasts between two stops. When a bus driver needs to go from a starting stop to a destination stop, there are two ways to get there. One way is going forward through the stops in the middle, and the other way is going the long way around the circle in the opposite direction.
The code starts by finding the total length of the whole circle by adding up all the bits of the road. Then, it adds up the pieces of the road that connect the starting stop to the destination stop to see how long that direct path is. After finding that number, the code looks at the whole circle and takes away the path that was just measured. This leaves the length of the path going the other way around. Finally, the code compares the short path and the long path to see which one is the smallest.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | ||||||||||
| www | AlgoMonster | C++ | Python | Java | TS | ||||||
| WalkCCC | C++ | Python | Java | ||||||||
| leetcode.ca | C++ | Python | JS | Java | Go | Rust | TS | ||||
| Progiez | C++ | Python | Java | ||||||||
| github | BigEggStudy | C# | |||||||||
| black-shadows | C++ | ||||||||||
| charles-wangkai | Java | ||||||||||
| DimitrisJim | C | ||||||||||
| everthis | JS | ||||||||||
| fartem | Ruby | ||||||||||
| fsq | C++ | ||||||||||
| Garvit244 | Python | ||||||||||
| halfrost | Go | ||||||||||
| JoshCrozier | JS | ||||||||||
| keineahnung2345 | C++ | ||||||||||
| lkwq007 | Python | ||||||||||
| lzl124631x | C++ | ||||||||||
| MacJim | C++ | ||||||||||
| suxrobGM | C# | ||||||||||
| varunu28 | Java | ||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||||
| WalkCCC | C++, Python, Java | ||||||||||
| leetcode.ca | C++, Go, Java, JavaScript, Python, Rust, TypeScript | ||||||||||
| Progiez | C++, Java, Python | ||||||||||
| BigEggStudy | C# | ||||||||||
| black-shadows | C++, C++ | ||||||||||
| charles-wangkai | Java | ||||||||||
| DimitrisJim | C | ||||||||||
| everthis | JavaScript | ||||||||||
| fartem | Ruby | ||||||||||
| fsq | C++ | ||||||||||
| Garvit244 | Python | ||||||||||
| halfrost | Go | ||||||||||
| JoshCrozier | JavaScript | ||||||||||
| keineahnung2345 | C++ | ||||||||||
| lkwq007 | Python | ||||||||||
| lzl124631x | C++ | ||||||||||
| MacJim | C++ | ||||||||||
| suxrobGM | C# | ||||||||||
| varunu28 | Java |
Videos
Similar Problems
- problem 2361: Minimum Costs Using the Train Line
Solved On The Same Day
- problem 1342: Number of Steps to Reduce a Number to Zero
- problem 1399: Count Largest Group
- problem 1496: Path Crossing
- problem 1646: Get Maximum in Generated Array
- problem 1893: Check if All the Integers in a Range Are Covered
- problem 2404: Most Frequent Even Element
- problem 2432: The Employee That Worked on the Longest Task
- problem 2451: Odd String Difference
- problem 2540: Minimum Common Value
- problem 609: Find Duplicate File in System
- problem 1169: Invalid Transactions
- problem 1711: Count Good Meals
- problem 1781: Sum of Beauty of All Substrings
- problem 1865: Finding Pairs With a Certain Sum
- problem 1871: Jump Game VII
- problem 2013: Detect Squares
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality