algoadvance

Leetcode 1184. Distance Between Bus Stops

Problem Statement:

You have a circular route of bus stops represented as an array where distance[i] is the distance between the i-th bus stop and the (i+1)th bus stop (with the route wrapping around such that distance[n-1] is the distance between the n-1th bus stop and the 0th bus stop). Given a start and destination stop, you are to find the shortest distance between the two stops.

Implement the function:

int distanceBetweenBusStops(vector<int>& distance, int start, int destination);

Clarifying Questions:

1. Q: Is start always less than destination, or can they be in any order? A: They can be in any order. So you need to consider the direction in which you calculate the distance.

2. Q: Can start and destination be the same? A: No, according to the problem, start and destination will always be different.

Strategy:

1. Calculate the distance going clockwise from start to destination.
2. Calculate the total distance of the circle.
3. Calculate the distance going counterclockwise, which is the total distance minus the clockwise distance.
4. Return the minimum of the two distances.

Code:

#include <vector>
#include <algorithm>
using namespace std;

int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
    // If start is greater than destination, swap them to simplify the problem
    if (start > destination) {
        swap(start, destination);
    }
    
    int clockwiseDistance = 0;
    for (int i = start; i < destination; ++i) {
        clockwiseDistance += distance[i];
    }
    
    int totalDistance = 0;
    for (int i = 0; i < distance.size(); ++i) {
        totalDistance += distance[i];
    }
    
    int counterclockwiseDistance = totalDistance - clockwiseDistance;
    
    return min(clockwiseDistance, counterclockwiseDistance);
}

Time Complexity:

• O(n) where n is the length of the distance array. This is because we need to traverse the array once to compute the total sum and another traversal to compute the clockwise distance.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?