[leetcode] 1184. Distance between bus stops

subject

1184. The distance between bus stops

There are... On the circular bus route n Individual station , From 0 To n - 1 Number . We know the distance between each pair of adjacent bus stops ,distance[i] Indicates that the number is i The station and number are (i + 1) % n The distance between the stations .

The buses on the loop line can travel clockwise and counterclockwise .

Return passengers from the starting point start Destination destination The shortest distance between .

Example 1：

 Input ：distance = [1,2,3,4], start = 0, destination = 1
 Output ：1
 explain ： Bus stop  0  and  1  The distance between them is  1  or  9, The minimum is  1.

Example 2：

 Input ：distance = [1,2,3,4], start = 0, destination = 2
 Output ：3
 explain ： Bus stop  0  and  2  The distance between them is  3  or  7, The minimum is  3.

Example 3：

 Input ：distance = [1,2,3,4], start = 0, destination = 3
 Output ：4
 explain ： Bus stop  0  and  3  The distance between them is  6  or  4, The minimum is  4.

Tips ：

• 1 <= n <= 10^4
• distance.length == n
• 0 <= start, destination < n
• 0 <= distance[i] <= 10^4

Ideas

• It is equivalent to the minimum value of the sum of clockwise path and counterclockwise path

Code

class Solution:
    def distanceBetweenBusStops(self, distance: List[int], start: int, destination: int) -> int:
        if start>destination: start,destination = destination,start
        return min(sum(distance[start:destination]), sum(distance[destination:]) + sum(distance[:start]) )

Complexity

• Time complexity ：$O(n)$
• Spatial complexity ：$O(1)$