Distance Between Bus Stops - Practice Coding Problems

Distance Between Bus Stops - Problem

Array Easy

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.

Input & Output

Example 1 — Basic Circle

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

› Output: 1

💡 Note: Clockwise: distance[0] = 1. Counterclockwise: distance[3] + distance[2] + distance[1] = 4 + 3 + 2 = 9. Return min(1, 9) = 1.

Example 2 — Opposite Direction Better

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

› Output: 3

💡 Note: Clockwise: distance[0] + distance[1] = 1 + 2 = 3. Counterclockwise: distance[3] + distance[2] = 4 + 3 = 7. Return min(3, 7) = 3.

Example 3 — Equal Distances

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

› Output: 4

💡 Note: Clockwise: 1 + 2 + 3 = 6. Counterclockwise: 4. Return min(6, 4) = 4.

Constraints

1 ≤ n ≤ 10⁴
distance.length == n
0 ≤ start, destination < n
0 ≤ distance[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Circular bus route with distances [1,2,3,4] between consecutive stops

Process

Calculate distance in both clockwise and counterclockwise directions

Output

Return the minimum distance between start and destination

Key Takeaway

🎯 Key Insight: On a circle, there are exactly two paths between any two points - calculate both and take the minimum

Asked in

A Amazon 15 M Microsoft 8

The key insight is that on a circular route, there are only two possible paths between any two stops. The optimal approach calculates the total distance first, then finds one direction and deduces the other by subtraction. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Single Pass with Total	O(n)	O(1)	Calculate total distance first, then find one direction and subtract from total
Brute Force - Two Direction Calculation	O(n)	O(1)	Calculate distance in both clockwise and counterclockwise directions separately

Optimized - Single Pass with Total — Algorithm Steps

Calculate total distance of the entire circle
Calculate clockwise distance from start to destination
Counterclockwise distance = total - clockwise
Return minimum of both distances

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Total

Sum all distances in the circle: 1+5+3+2=11

One Direction

Calculate clockwise path: 1+5=6

Other Direction

Counterclockwise = Total - Clockwise = 11-6=5

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* distance, int distanceSize, int start, int destination) {
    // Calculate total distance
    int totalDistance = 0;
    for (int i = 0; i < distanceSize; i++) {
        totalDistance += distance[i];
    }
    
    // Calculate clockwise distance
    int clockwise = 0;
    int current = start;
    while (current != destination) {
        clockwise += distance[current];
        current = (current + 1) % distanceSize;
    }
    
    // Counterclockwise is total - clockwise
    int counterclockwise = totalDistance - clockwise;
    
    return clockwise < counterclockwise ? clockwise : counterclockwise;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int distance[100];
    int count = 0;
    char *token = strtok(line, "[],\n ");
    while (token != NULL) {
        distance[count++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    int start, destination;
    scanf("%d", &start);
    scanf("%d", &destination);
    
    int result = solution(distance, count, start, destination);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

One pass to calculate total, one pass to calculate one direction

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables to store distances

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Single Pass with Total — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler