Skip to content

1184. Distance Between Bus Stops

Description

A busΒ has n stops numbered from 0 to n - 1 that formΒ a circle. We know the distance between all pairs of neighboring stops where distance[i] is the distance between the stops numberΒ i and (i + 1) % n.

The bus goes along both directionsΒ i.e. clockwise and counterclockwise.

Return the shortest distance between the givenΒ startΒ and destinationΒ stops.

Β 

Example 1:


Input: distance = [1,2,3,4], start = 0, destination = 1

Output: 1

Explanation: Distance between 0 and 1 is 1 or 9, minimum is 1.

Β 

Example 2:


Input: distance = [1,2,3,4], start = 0, destination = 2

Output: 3

Explanation: Distance between 0 and 2 is 3 or 7, minimum is 3.

Β 

Example 3:


Input: distance = [1,2,3,4], start = 0, destination = 3

Output: 4

Explanation: Distance between 0 and 3 is 6 or 4, minimum is 4.

Β 

Constraints:

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

Solutions

Solution 1: Simulation

We can first calculate the total distance \(s\) that the bus travels, then simulate the bus's journey. Starting from the departure point, we move one stop to the right each time until we reach the destination, recording the travel distance \(t\) during this process. Finally, we return the minimum value between \(t\) and \(s - t\).

The time complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{distance}\). The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def distanceBetweenBusStops(
        self, distance: List[int], start: int, destination: int
    ) -> int:
        s = sum(distance)
        t, n = 0, len(distance)
        while start != destination:
            t += distance[start]
            start = (start + 1) % n
        return min(t, s - t)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int distanceBetweenBusStops(int[] distance, int start, int destination) {
        int s = Arrays.stream(distance).sum();
        int n = distance.length, t = 0;
        while (start != destination) {
            t += distance[start];
            start = (start + 1) % n;
        }
        return Math.min(t, s - t);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
        int s = accumulate(distance.begin(), distance.end(), 0);
        int t = 0, n = distance.size();
        while (start != destination) {
            t += distance[start];
            start = (start + 1) % n;
        }
        return min(t, s - t);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func distanceBetweenBusStops(distance []int, start int, destination int) int {
    s, t := 0, 0
    for _, x := range distance {
        s += x
    }
    for start != destination {
        t += distance[start]
        start = (start + 1) % len(distance)
    }
    return min(t, s-t)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function distanceBetweenBusStops(distance: number[], start: number, destination: number): number {
    const s = distance.reduce((a, b) => a + b, 0);
    const n = distance.length;
    let t = 0;
    while (start !== destination) {
        t += distance[start];
        start = (start + 1) % n;
    }
    return Math.min(t, s - t);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
impl Solution {
    pub fn distance_between_bus_stops(distance: Vec<i32>, start: i32, destination: i32) -> i32 {
        let s: i32 = distance.iter().sum();
        let mut t = 0;
        let n = distance.len();
        let mut start = start as usize;
        let destination = destination as usize;

        while start != destination {
            t += distance[start];
            start = (start + 1) % n;
        }

        t.min(s - t)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
/**
 * @param {number[]} distance
 * @param {number} start
 * @param {number} destination
 * @return {number}
 */
var distanceBetweenBusStops = function (distance, start, destination) {
    const s = distance.reduce((a, b) => a + b, 0);
    const n = distance.length;
    let t = 0;
    while (start !== destination) {
        t += distance[start];
        start = (start + 1) % n;
    }
    return Math.min(t, s - t);
};

Comments