{x}
blog image

Partition Array Such That Maximum Difference Is K

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

Solution Explanation: Greedy Approach with Sorting

This problem can be efficiently solved using a greedy approach combined with sorting. The core idea is to minimize the number of subsequences by strategically assigning elements to existing subsequences whenever possible. This is done by maintaining a running "minimum" for each subsequence.

Algorithm:

  1. Sort: First, sort the input array nums in ascending order. This allows us to process elements in a way that naturally leads to minimizing the number of subsequences.

  2. Iterate and Assign: Iterate through the sorted nums. We maintain a variable min_val to track the minimum value currently assigned to a subsequence. Initially, min_val is set to the first element of the sorted array.

  3. Subsequence Creation: For each element curr_val in nums:

    • If curr_val - min_val <= k, it means we can add curr_val to the current subsequence without violating the maximum difference constraint.
    • If curr_val - min_val > k, it implies that curr_val cannot be added to the current subsequence. We must create a new subsequence, starting with curr_val as its minimum (min_val is updated to curr_val), and increment our subsequence count.

  4. Return Subsequence Count: After iterating through all elements, the final count of subsequences represents the minimum number required to satisfy the given constraints.

Time Complexity: O(N log N), dominated by the sorting step. The iteration through the sorted array takes linear time, O(N).

Space Complexity: O(log N) or O(1) depending on the sorting implementation. In-place sorting algorithms like heapsort have O(log N) space complexity, while others might have O(1). The additional space used by variables is constant.

Code Examples (Python):

def partitionArray(nums: list[int], k: int) -> int:
    nums.sort()  # Sort the array
    subsequences = 1  # Initialize count of subsequences
    min_val = nums[0]  # Initialize minimum value for the first subsequence
 
    for num in nums[1:]: #Start from second element, as the first is already assigned
        if num - min_val > k:
            subsequences += 1
            min_val = num  # Start a new subsequence
        # else, the current num can be added to the existing subsequence
 
    return subsequences

Other Languages (Conceptual): The core algorithm remains the same across different programming languages. The only differences would be in the syntax for sorting and array handling. For example, in Java, you would use Arrays.sort(nums) and for-each loop. C++ would use std::sort(nums.begin(), nums.end()). The logic of comparing and creating new subsequences would remain identical.

Example:

Let's consider nums = [3, 6, 1, 2, 5] and k = 2.

  1. Sorted nums: [1, 2, 3, 5, 6]
  2. Iteration:
    • min_val = 1
    • 2 - 1 <= 2 (add 2 to the subsequence)
    • 3 - 1 <= 2 (add 3 to the subsequence)
    • 5 - 1 > 2 (new subsequence, min_val = 5)
    • 6 - 5 <= 2 (add 6 to the subsequence)
  3. Result: 2 subsequences ([1, 2, 3], [5, 6])