Distance Between Bus Stops

Easy
1101.

Distance Between Bus Stops

Distance Between Bus Stops is an easy coding problem on arrays and prefix sum, asked in Amazon and Google interviews.

A bus line is a loop of n stops numbered 0 to n - 1. distance[i] is the length of the road between stop i and stop (i + 1) % n, and the bus may travel the loop in either direction.

Return the length of the shorter way round from stop start to stop destination.

Example 1

Input
distance = [4,1,6,2], start = 3, destination = 1
Output
6
Explanation
Going 3 → 0 → 1 costs 2 + 4 = 6; going 3 → 2 → 1 costs 6 + 1 = 7.

Example 2

Input
distance = [5,8,2], start = 0, destination = 2
Output
2

Example 3

Input
distance = [2,5,9,1], start = 1, destination = 1
Output
0

Constraints

  • 1 <= n <= 10^4
  • distance.length == n
  • 0 <= start, destination < n
  • 0 <= distance[i] <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} distance
 * @param {number} start
 * @param {number} destination
 * @return {number}
 */
var distanceBetweenBusStops = function(distance, start, destination) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Distance Between Bus Stops — Solution in Python, Java & C++

Distance Between Bus Stops solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Distance Between Bus Stops is an easy coding problem on arrays and prefix sum, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Arrays, Prefix Sum
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A bus line is a loop of n stops numbered 0 to n - 1. distance[i] is the length of the road between stop i and stop (i + 1) % n, and the bus may travel the loop in either direction.

Return the length of the shorter way round from stop start to stop destination.

Example 1

Input: distance = [4,1,6,2], start = 3, destination = 1
Output: 6
Explanation: Going 3 → 0 → 1 costs 2 + 4 = 6; going 3 → 2 → 1 costs 6 + 1 = 7.

Example 2

Input: distance = [5,8,2], start = 0, destination = 2
Output: 2

Example 3

Input: distance = [2,5,9,1], start = 1, destination = 1
Output: 0

Constraints

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

Hints for Distance Between Bus Stops

  1. Hint 1

    There are only two routes: clockwise and counter-clockwise.

  2. Hint 2

    The two routes together cover the whole loop exactly once.

  3. Hint 3

    Sum the segments between the smaller and the larger stop index; the other route is the loop total minus that.

How to solve Distance Between Bus Stops

The clockwise and counter-clockwise routes split the loop between them, so one sum and the loop's total give both lengths.

Approach

  1. Let lo = min(start, destination) and hi = max(start, destination).
  2. Sum distance[lo..hi-1] — the route that does not cross stop 0's back edge — and the whole array.
  3. Return the smaller of that sum and total - sum.

Why it works

Travelling from lo up to hi uses exactly the segments lo through hi - 1; the other direction uses every remaining segment. Distance is symmetric, so swapping start and destination changes nothing, and the answer is the smaller of the two complementary sums.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • start may be larger than destination — normalise the pair first.
  • When start == destination the answer is 0.
  • Segment i joins stop i to stop i + 1, so the range is lo to hi - 1, not hi.

Reference solution

Python

from typing import List

def distanceBetweenBusStops(distance: List[int], start: int, destination: int) -> int:
    lo, hi = min(start, destination), max(start, destination)
    inner = sum(distance[lo:hi])
    return min(inner, sum(distance) - inner)

Java

public static int distanceBetweenBusStops(int[] distance, int start, int destination) {
    int lo = Math.min(start, destination), hi = Math.max(start, destination);
    int total = 0, inner = 0;
    for (int i = 0; i < distance.length; i++) {
        total += distance[i];
        if (i >= lo && i < hi) inner += distance[i];
    }
    return Math.min(inner, total - inner);
}

C++

int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
    int lo = min(start, destination), hi = max(start, destination);
    int total = 0, inner = 0;
    for (int i = 0; i < (int)distance.size(); i++) {
        total += distance[i];
        if (i >= lo && i < hi) inner += distance[i];
    }
    return min(inner, total - inner);
}

JavaScript

var distanceBetweenBusStops = function(distance, start, destination) {
    var lo = Math.min(start, destination), hi = Math.max(start, destination);
    var total = 0, inner = 0;
    for (var i = 0; i < distance.length; i++) {
        total += distance[i];
        if (i >= lo && i < hi) inner += distance[i];
    }
    return Math.min(inner, total - inner);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Prefix Sum