Minimize Maximum Adjacent Distance

Moderate

0/80

0 upvote

Asked in company

Problem statement

You are given the positions of N cubes on a 1D line, represented by an array X. You are allowed to remove at most K cubes from this line.

Your goal is to find a configuration of remaining cubes that minimizes the maximum distance between any two adjacent cubes.

For example, if the remaining cubes are at positions [1, 5, 12], the adjacent distances are (5-1)=4 and (12-5)=7. The maximum adjacent distance is 7.

You need to find the minimum possible value for this maximum adjacent distance.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains two space-separated integers, N (the number of cubes) and K (the maximum number of cubes you can remove).

The second line contains N space-separated integers, representing the positions of the cubes in array X.

Output Format:

Print a single integer representing the minimum possible maximum distance between any two adjacent remaining cubes.

Note:

The problem asks for the "minimum of a maximum," which is a strong indicator for Binary Search.

Sample Input 1:

5 2
1 2 4 7 8

Sample Output 1:

Explanation for Sample 1:

The sorted cube positions are [1, 2, 4, 7, 8].
We can perform at most 2 operations (insert or adjust up to 2 gaps).

If we aim for a maximum allowed distance of 2:

  The large gap 7 - 4 = 3 can be “fixed” with one operation (splitting it into two segments of at most length 2).

  All other gaps are already ≤ 2.

We need only 1 operation, which is ≤ K = 2.

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

2 <= N <= 10^5
0 <= K < N - 1
0 <= X[i] <= 10^9

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Minimize Maximum Adjacent Distance

Console