Maximize Minimum Difference
MediumPractice library · +20 XPbinary searchgreedy
Given N distinct integers sorted in non-decreasing order, select K of them such that the minimum difference between any two selected integers is maximized. Print this maximum possible minimum difference.
Input
The first line contains two integers N and K, separated by a space. The second line contains N space-separated integers, a_1, a_2, ..., a_N, which are sorted in non-decreasing order.
Output
Print a single integer: the maximum possible minimum difference between any two selected integers.
Constraints
1 <= K <= N <= 200000; 1 <= a_1 < a_2 < ... < a_N <= 10^9
Time limit 2 s (native code; slower languages get more)Memory 256 MB14 hidden tests
Example 1
Input
5 3 1 2 4 8 9
Output
3
Selecting 1, 4, 8 gives minimum difference 3. Selecting 1, 4, 9 gives min diff 3. Selecting 2, 8, 9 gives min diff 1. Max possible min diff is 3.
Example 2
Input
4 2 10 20 30 40
Output
30
Select 10 and 40. Min diff is 30.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 3 1 2 4 8 9
Example 2 input
4 2 10 20 30 40