We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Partition Array Such That Maximum Difference Is K

Number: 2387

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an integer array nums and an integer k, partition nums into one or more subsequences so that every element appears in exactly one subsequence and the difference between the maximum and minimum value in each subsequence is at most k. Return the minimum number of subsequences required.

Key Insights

  • Sorting the array helps group numbers that are close in value.
  • A greedy strategy can be applied by iterating through the sorted array and starting a new subsequence whenever the difference from the start of the current subsequence exceeds k.
  • Since subsequences preserve the original order, sorting does not break the requirement because we are free to pick any elements as long as order is kept, and the sorted order is a valid order.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting, with an additional O(n) for the linear scan. Space Complexity: O(n) due to the auxiliary space for sorting.

Solution

The approach involves two main steps. First, sort the input array. Then, iterate over the sorted array while maintaining the starting element of the current subsequence. If the difference between the current element and the starting element exceeds k, then the current subsequence cannot include this element; hence, increment the count of subsequences and start a new subsequence from the current element. This greedy grouping ensures that each subsequence has a maximum difference that does not exceed k while minimizing the total number of subsequences.

Code Solutions

# Define a function to partition the array based on the condition provided.
def partitionArray(nums, k):
    # Sort the input list since it helps group close values together.
    nums.sort()
    
    # Initialize the count of subsequences.
    subsequences = 1
    
    # Set the first element as the start of the current subsequence.
    start_value = nums[0]
    
    # Iterate through the sorted list starting from the second element.
    for num in nums:
        # If the difference between the current element and the subsequence start is greater than k,
        # a new subsequence must be started.
        if num - start_value > k:
            subsequences += 1
            start_value = num  # Reset the start of the new subsequence.
    
    return subsequences

# Example usage:
print(partitionArray([3, 6, 1, 2, 5], 2))
← Back to All Questions