Partition Array Such That Maximum Difference Is K
MedPrompt
You are given an integer array nums and an integer k. You may partition nums into one or more subsequences such that each element in nums appears in exactly one of the subsequences.
Return 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.
Example 1:
Input: nums = [3,6,1,2,5], k = 2
Output: 2
Explanation:
We can partition nums into the two subsequences [3,1,2] and [6,5].
The difference between the maximum and minimum value in the first subsequence is 3 - 1 = 2.
The difference between the maximum and minimum value in the second subsequence is 6 - 5 = 1.
Since two subsequences were created, we return 2. It can be shown that 2 is the minimum number of subsequences needed.Example 2:
Input: nums = [1,2,3], k = 1
Output: 2
Explanation:
We can partition nums into the two subsequences [1,2] and [3].
The difference between the maximum and minimum value in the first subsequence is 2 - 1 = 1.
The difference between the maximum and minimum value in the second subsequence is 3 - 3 = 0.
Since two subsequences were created, we return 2. Note that another optimal solution is to partition nums into the two subsequences [1] and [2,3].Example 3:
Input: nums = [2,2,4,5], k = 0
Output: 3
Explanation:
We can partition nums into the three subsequences [2,2], [4], and [5].
The difference between the maximum and minimum value in the first subsequences is 2 - 2 = 0.
The difference between the maximum and minimum value in the second subsequences is 4 - 4 = 0.
The difference between the maximum and minimum value in the third subsequences is 5 - 5 = 0.
Since three subsequences were created, we return 3. It can be shown that 3 is the minimum number of subsequences needed.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 1050 <= k <= 105
Approaches
2 approaches with complexity analysis and trade-offs.
This approach is based on the key observation that to minimize the number of subsequences, we should make each subsequence as "full" as possible. Since the problem deals with subsequences, the original order of elements does not matter. This allows us to sort the array first. After sorting, we can greedily form subsequences. We start a new subsequence with the smallest available element and include all subsequent elements that fit within the k difference constraint.
Algorithm
- If the input array
numsis empty, return 0. - Sort the array
numsin non-decreasing order. - Initialize a counter for the number of subsequences,
partitions, to 1. - Set the minimum value of the current subsequence,
minVal, to the first element of the sorted array,nums[0]. - Iterate through the sorted array starting from the second element (
i = 1ton-1):- For each element
nums[i], check if the differencenums[i] - minValis greater thank. - If it is, the current element
nums[i]cannot be part of the current subsequence. We must start a new one. - To do this, increment
partitionsand updateminValtonums[i].
- For each element
- After the loop finishes, return the total
partitionscount.
Walkthrough
The core idea is that if we sort the array nums, we can process the elements in increasing order. This simplifies the problem of finding the minimum and maximum within a potential subsequence.
We initialize the count of subsequences to 1 and take the first element of the sorted array, nums[0], as the minimum value (minVal) for our first subsequence.
We then iterate through the rest of the sorted array. Any element nums[i] can be added to the current subsequence as long as nums[i] - minVal <= k. Since the array is sorted, we are guaranteed that nums[i] will be the maximum element considered so far for the current subsequence, and minVal will remain the minimum.
When we encounter an element nums[j] such that nums[j] - minVal > k, we know that nums[j] (and all elements after it, due to the sorted order) cannot belong to the current subsequence. At this point, we must finalize the current subsequence and start a new one. We do this by incrementing our subsequence counter and setting nums[j] as the minVal for this new subsequence.
This greedy process is repeated until all elements in the sorted array have been placed into a subsequence. The final count is guaranteed to be the minimum number of subsequences required.
import java.util.Arrays; class Solution { public int partitionArray(int[] nums, int k) { if (nums == null || nums.length == 0) { return 0; } Arrays.sort(nums); int partitions = 1; int minVal = nums[0]; for (int i = 1; i < nums.length; i++) { if (nums[i] - minVal > k) { partitions++; minVal = nums[i]; } } return partitions; }}Complexity
Time
O(N log N), where N is the number of elements in `nums`. The `Arrays.sort()` method takes O(N log N) time. The subsequent single pass through the array takes O(N) time. Thus, the total time complexity is dominated by the sorting step.
Space
O(log N) or O(N). The space complexity depends on the implementation of the sorting algorithm used. `Arrays.sort()` in Java for primitive types uses a dual-pivot quicksort, which has an average space complexity of O(log N) for the recursion stack. The worst-case space complexity can be O(N).
Trade-offs
Pros
The greedy logic is simple and intuitive.
The implementation is straightforward.
It is a general approach that works for any range of numbers, as its performance only depends on the number of elements
N.
Cons
The time complexity is dominated by the sorting step, which is O(N log N). This can be slower than linear-time approaches if the range of values in the array is constrained and allows for faster sorting methods like counting sort.
Solutions
Solution
public class Solution { public int PartitionArray(int[] nums, int k) { Array.Sort(nums); int ans = 1; int a = nums[0]; foreach(int b in nums) { if (b - a > k) { a = b; ans++; } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.