488. Partition Array to Minimize Difference
0
Medium
Given an array of integers nums and an integer k, you need to partition nums into one or more subsequences. Each element in nums must appear in exactly one subsequence. Find the minimum number of subsequences needed such that the difference between the maximum and minimum values in each subsequence is at most k. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Input Format
The first line of input contains two space-separated integers N (the size of the array) and K. The second line consists of N space-separated integers representing the elements of the array.
Output Format
Output an integer representing the minimum number of subsequences required.
Example
Input
5 2
3 6 1 2 5
Output
2
Constraints
1 <= N <= 10^4
Loading...
View Submissions
Console