Minimize Max Distance to Gas Station - Practice Coding Problems

Minimize Max Distance to Gas Station - Problem

You are given an integer array stations that represents the positions of gas stations on the x-axis. You are also given an integer k.

You should add k new gas stations. You can add the stations anywhere on the x-axis, and not necessarily on an integer position.

Let penalty() be the maximum distance between adjacent gas stations after adding the k new stations.

Return the smallest possible value of penalty().

Answers within 10^-6 of the actual answer will be accepted.

Input & Output

Example 1 — Basic Case

$ Input: stations = [1,3,6,10], k = 1

› Output: 3.0

💡 Note: Initial gaps are [2,3,4]. Adding one station optimally in the gap of 4 (between 6 and 10) at position 8 gives gaps [2,3,2,2]. Maximum gap is 3.0.

Example 2 — Multiple Additions

$ Input: stations = [23,24,36,39,46,56,57,65,84,98], k = 1

› Output: 14.0

💡 Note: Largest gap is 84-65=19. Adding one station at 74.5 splits it into two gaps of 9.5 each. New maximum gap becomes 14 (between 46 and 56).

Example 3 — Minimum Input

$ Input: stations = [1,2], k = 1

› Output: 0.5

💡 Note: Initial gap is 1. Adding one station at 1.5 creates two gaps of 0.5 each. Maximum gap is 0.5.

Constraints

2 ≤ stations.length ≤ 2000
0 ≤ stations[i] ≤ 10⁸
stations is sorted in a strictly increasing order
1 ≤ k ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Gas stations at positions [1,3,6,10] with k=1 new station

Process

Find largest gap (4 between stations 6 and 10) and split optimally

Output

New maximum gap reduced to 3.0

Key Takeaway

🎯 Key Insight: Binary search on the answer space is more efficient than searching position space

Asked in

G Google 25 a Amazon 18

The key insight is to use binary search on the answer space rather than trying all possible station placements. We binary search on the maximum distance value and check if it's achievable with k stations. The optimal approach has Time: O(n log(max_distance)), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy with Priority Queue	O(k log n)	O(n)	Always add a station to the segment with maximum distance
Binary Search on Answer	O(n log(max_distance))	O(1)	Binary search on the maximum distance value

Greedy with Priority Queue — Algorithm Steps

Calculate initial distances between adjacent stations
Use max heap to track segments by distance
For each of k stations, split the longest segment in half

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Gaps

Calculate distances between adjacent stations

Priority Queue

Track segments by their maximum distance

Split Largest

Add station to middle of largest gap, update queue

Code -

solution.c — C

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

struct Segment {
    double currentGap;
    double originalGap;
    int divisions;
};

int compare(const void* a, const void* b) {
    struct Segment* segA = (struct Segment*)a;
    struct Segment* segB = (struct Segment*)b;
    if (segA->currentGap < segB->currentGap) return 1;
    if (segA->currentGap > segB->currentGap) return -1;
    return 0;
}

double solution(int* stations, int stationsSize, int k) {
    if (stationsSize < 2) return 0.0;
    
    struct Segment* segments = malloc((stationsSize - 1) * sizeof(struct Segment));
    int segCount = 0;
    
    // Calculate initial gaps
    for (int i = 0; i < stationsSize - 1; i++) {
        double gap = stations[i + 1] - stations[i];
        segments[segCount].currentGap = gap;
        segments[segCount].originalGap = gap;
        segments[segCount].divisions = 1;
        segCount++;
    }
    
    // Add k stations
    for (int i = 0; i < k; i++) {
        qsort(segments, segCount, sizeof(struct Segment), compare);
        segments[0].divisions++;
        segments[0].currentGap = segments[0].originalGap / segments[0].divisions;
    }
    
    qsort(segments, segCount, sizeof(struct Segment), compare);
    double result = segments[0].currentGap;
    free(segments);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int stations[1000];
    int count = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            stations[count++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    double result = solution(stations, count, k);
    printf("%f\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k log n)

k iterations, each with O(log n) heap operations

⚡ Linearithmic

Space Complexity

O(n)

Priority queue stores up to n segments

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 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

Greedy with Priority Queue — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler