{x}
blog image

Distance Between Bus Stops

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

Solution Explanation for 1184. Distance Between Bus Stops

This problem involves finding the shortest distance between two bus stops on a circular route. The solution leverages the fact that the shortest distance is either the clockwise or counter-clockwise distance.

Approach:

  1. Calculate Total Distance: First, we calculate the total distance (s) around the entire circular route by summing all the distances in the distance array.

  2. Calculate Direct Distance: We then simulate traveling from the start stop to the destination stop in one direction (clockwise). We accumulate the distance (t) along this path.

  3. Determine Shortest Distance: The shortest distance is the minimum between the directly calculated distance (t) and the remaining distance obtained by subtracting the direct distance from the total distance (s - t). This accounts for the counter-clockwise path.

Time and Space Complexity Analysis:

  • Time Complexity: O(n), where n is the number of stops. This is because we iterate through the distance array once to calculate the total distance and then iterate at most n times in the while loop to calculate the direct distance.

  • Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size.

Code Implementation in Multiple Languages:

The code implementations below follow the described approach. They all have the same core logic, differing only in syntax.

Python3:

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)

Java:

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);
    }
}

C++:

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);
    }
};

Go:

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)
}
 
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

TypeScript:

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);
}

Rust:

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)
    }
}

JavaScript:

/**
 * @param {number[]} distance
 * @param {number} start
 * @param {number} destination
 * @return {number}
 */
var distanceBetweenBusStops = function(distance, start, destination) {
    let totalDistance = distance.reduce((sum, dist) => sum + dist, 0);
    let currentDistance = 0;
    let currentStop = start;
 
    while (currentStop != destination) {
        currentDistance += distance[currentStop];
        currentStop = (currentStop + 1) % distance.length;
    }
 
    return Math.min(currentDistance, totalDistance - currentDistance);
};

These code snippets all efficiently solve the problem by following the outlined approach, achieving optimal time and space complexity. They demonstrate the core logic in various programming languages, highlighting the adaptability of the solution.