Problem 1184

Abstract / Summary

Given a circular route with bus stops and their positions, find the shorter distance between two specified stops.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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)
7 lines | 316 bytes | submitted December 12, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 56% (100k+ submissions).

Typical patterns to solve this problem:
  • Array
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 8 | μ = 7.96 | σ = 1.37

Complexity Analysis

Time: linear
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
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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
33 links | 20 authors | 10 languages

Videos

4 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

17 solutions   December 12, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • 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