Minimize Maximum Difference of Elements in Intervals
Given an array of N integers, you need to partition it into K contiguous subarrays. Your goal is to minimize the maximum difference between the largest and smallest element within any subarray. Output this minimum possible maximum difference.
Input
The first line contains two integers N and K. The second line contains N space-separated integers, representing the array elements.
Output
Print a single integer: the minimum possible maximum difference.
Constraints
1 <= N <= 200000 1 <= K <= N 0 <= array elements <= 10^9
Example 1
5 2 1 5 2 8 3
5
Partition into [1, 5, 2] and [8, 3]. Differences are 5-1=4 and 8-3=5. Max difference is 5. Another partition: [1, 5] and [2, 8, 3]. Differences are 5-1=4 and 8-2=6. Max difference is 6. Minimal max difference is 5.
Example 2
7 3 10 20 30 5 15 25 40
20
Partition [10, 20, 30], [5, 15, 25], [40]. Differences are 20, 20, 0. Max difference is 20. This is optimal.
Hints
Similar problems
- Find Minimums in Sliding WindowsMedium
- Maximize Distinct Elements After OperationsMedium
- Distinct Elements with Minimum Total CostMedium
- Longest Subarray with Limited DifferenceMedium
- Distinct Element Sum with Minimum CostMedium
- Process Tasks by DeadlineMedium
More topics: Sliding Window problems, Greedy problems, Heap and Priority Queue problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 2 1 5 2 8 3
7 3 10 20 30 5 15 25 40