Scale Engineer

Partition Array Such That Maximum Difference Is K

Med
#2091Time: 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).
Patterns
Greedy
Algorithms
Sorting
Data structures
Array

Prompt

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 <= 105
  • 0 <= nums[i] <= 105
  • 0 <= 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 nums is empty, return 0.
  • Sort the array nums in 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 = 1 to n-1):
    • For each element nums[i], check if the difference nums[i] - minVal is greater than k.
    • 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 partitions and update minVal to nums[i].
  • After the loop finishes, return the total partitions count.

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

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.

← Previous

Previous problem

Next →

Next problem