Partition Array Such That Maximum Difference Is K
Understanding the Problem
We need to split an array into the fewest possible groups (subsequences) where, within each group, the gap between the largest and smallest element is at most k.
Although the problem talks about subsequences, the original order of elements is irrelevant: a group's max-min difference depends only on which values it contains. Grouping [3,1,2] or [1,2,3] gives the same range (3 - 1 = 2). The problem reduces to partitioning a collection of numbers into the fewest groups where each group's range is at most k.
Sorting is therefore the first step. Once sorted, elements that can share a group sit next to each other, and skipping over a sorted element to include a later one in the same group can only widen the range.
Key Constraints:
1 <= nums.length <= 10^5→ With n up to 100,000, an O(n^2) approach performs around 10^10 operations and is too slow. We need O(n log n) or better. Sorting is O(n log n), and the greedy pass after it is O(n).0 <= nums[i] <= 10^5→ Values are non-negative and bounded, which would permit counting sort, but a standard comparison sort already meets the time budget.0 <= k <= 10^5→ k can be 0, meaning a group can only contain equal elements. It can also exceed the value range, meaning everything fits in one group. Both extremes are edge cases to check.
Approach 1: Brute Force (Check All Groups)
Intuition
Sort the array, then place each element into the first existing group that can take it. A group can accept a new element if the difference between that element and the group's minimum is at most k. If no existing group works, start a new one.
This first-fit check is valid because, after sorting, the element being placed is the largest seen so far. Adding it to a group can only raise the group's max, so the only comparison needed is against the group's min, which never changes after the group is created.
The cost is in the scan. In the worst case (k = 0 with all distinct elements), every element starts its own group, and each new element scans every existing group before failing. That is O(n^2).
Algorithm
- Sort
numsin ascending order. - Maintain a list of groups, where each group stores its minimum value.
- For each element in the sorted array:
- Scan through existing groups to find one where
element - group_min <= k. - If found, add the element to that group.
- If no valid group is found, create a new group with this element as its minimum.
- Return the total number of groups.
Example Walkthrough
Code
- Time Complexity: O(n^2). Sorting takes O(n log n). Then for each of the n elements, we scan through up to n groups in the worst case. The scan dominates at O(n^2).
- Space Complexity: O(n). The groupMins list can hold up to n entries when every element forms its own group.
The scan over all groups is unnecessary. Group minimums increase in the order groups are created, so an element that fails the most recently created group fails every group. Tracking only the current group's minimum produces the same partition count in a single pass over the sorted array.
Approach 2: Greedy with Sorting (Optimal)
Intuition
After sorting, an optimal partition can always use contiguous runs of the array. If sorted values a <= b <= c have a and c in the same group but not b, then b can be moved into that group: c - a <= k implies b - a <= k, and adding b does not change the group's range because c is already the max and a the min.
With contiguity established, the algorithm is a single sweep. Start a group with the current element as its minimum, keep moving right while nums[i] - groupMin <= k, and start a new group at the first element that exceeds the range. The answer is the number of groups started.
An exchange argument shows that extending each group as far as possible is optimal. Take any optimal partition of the sorted array into contiguous segments and compare it with the greedy one at the first boundary where they differ. The greedy segment is the longest valid run starting at that position, so the optimal segment ends earlier. Move the optimal boundary right to match the greedy one: the first segment stays valid (the greedy already verified every element in it), and the next segment loses elements from its left end, which can only raise its minimum and shrink its range. The group count does not increase. Repeating this at each boundary transforms the optimal partition into the greedy one, so the greedy partition uses the minimum number of groups.
Algorithm
- Sort
numsin ascending order. - Initialize
partitions = 1(we always need at least one group). - Set
groupMin = nums[0](the first group starts with the smallest element). - For each element from index 1 to n - 1:
- If
nums[i] - groupMin > k, the element cannot fit in the current group. Start a new group: incrementpartitionsand setgroupMin = nums[i]. - Otherwise, the element joins the current group and nothing changes.
- Return
partitions.
Example Walkthrough
Code
- Time Complexity: O(n log n). Sorting takes O(n log n). The greedy scan visits each element exactly once, taking O(n). The sort dominates.
- Space Complexity: O(1) extra space. The greedy scan uses only a couple of variables. The sort itself may use O(log n) to O(n) space depending on the language.