algoadvance

Leetcode 1184. Distance Between Bus Stops

Problem Statement

You are given an integer array distance where distance[i] describes the distance between the i-th bus stop and the (i+1)-th bus stop. You are also given two integers start and destination that indicate the start and destination stops, respectively (the bus stops are in a circular route).

Return the shortest distance between these two stops.

Clarifying Questions

  1. Can start be greater than destination?
    • Yes, since the bus routes are circular, the start can be either greater than or less than destination.
  2. Will the input array be non-empty and contain positive integers?
    • Yes, the input array distance will always be non-empty and contain positive integers.
  3. Are the indices always valid (i.e., within the bounds of the array)?
    • Yes, start and destination will always be valid indices of the array.
  4. Can start be equal to destination?
    • Yes, if start equals destination, the shortest distance is zero.

Strategy

  1. Calculate the Clockwise Distance: Traverse the bus stops from start to destination in a clockwise direction and sum the distances.
  2. Calculate the Counter-Clockwise Distance: Traverse the bus stops from destination to start in a clockwise direction and sum the distances.
  3. Return the Minimum: The result will be the minimum of the two computed distances.

Code

public class Solution {
    public int distanceBetweenBusStops(int[] distance, int start, int destination) {
        if (start == destination) {
            return 0;
        }

        int totalDistance = 0;
        for (int dist : distance) {
            totalDistance += dist;
        }

        int clockwiseDistance = 0;
        int counterClockwiseDistance = 0;
        
        int i = start;
        while (i != destination) {
            clockwiseDistance += distance[i];
            i = (i + 1) % distance.length;
        }
        
        counterClockwiseDistance = totalDistance - clockwiseDistance;
        
        return Math.min(clockwiseDistance, counterClockwiseDistance);
    }
}

Time Complexity

Analysis

  1. Space Complexity: O(1) because only a few extra variables are used for calculation.
  2. Edge Cases:
    • The start is the same as the destination.
    • Small arrays, e.g., with 1 or 2 elements.
    • Circular calculation when the destination is before the start in the array.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI