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

Minimize the Maximum Difference of Pairs

Number: 2720

Difficulty: Medium

Paid? No

Companies: Amazon, Apple, Microsoft, Navi

Problem Description

Given an array of integers and an integer p, form p disjoint pairs (i.e. no index is used more than once) such that the maximum absolute difference among the pairs is minimized. The difference for a pair (i, j) is defined as |nums[i] - nums[j]|. Return the minimized maximum difference.

Key Insights

  • Sorting the array clusters numbers with small differences together.
  • Use binary search to decide on a candidate maximum difference.
  • For each candidate difference during binary search, use a greedy strategy to form pairs:
    • Iterate through the sorted array.
    • Whenever the difference between consecutive numbers is less than or equal to the candidate, form a pair and skip the next element.
  • The goal is to check if at least p pairs can be formed with a candidate difference.

Space and Time Complexity

Time Complexity: O(n log n + n log(max(nums) - min(nums))) Space Complexity: O(n) (for sorting)

Solution

We first sort the array to bring numbers with small differences closer together. Then we use binary search on the possible range of maximum differences. For each candidate value during the binary search, we use a greedy approach to try to form at least p pairs. We iterate through the array and whenever the difference between nums[i] and nums[i+1] is less than or equal to the candidate maximum, we form a pair and move the index forward by two. If we can form p pairs, the candidate value might be too high, and we reduce the range; otherwise we increase it. This balance ensures that we find the smallest candidate maximum difference that allows p pairs.

Code Solutions

# Python solution with detailed comments

def minimizeMaxDifference(nums, p):
    # Sort the array to facilitate pairing adjacent numbers
    nums.sort()
    
    # Function to check if at least p pairs can be formed
    # with maximum difference <= candidate
    def can_form_pairs(candidate):
        count = 0
        i = 0
        # Iterate through the sorted array
        while i < len(nums) - 1:
            # If the difference between adjacent elements is within candidate, form a pair.
            if nums[i+1] - nums[i] <= candidate:
                count += 1  # A valid pair is formed
                i += 2    # Move past this pair
            else:
                i += 1
            # Early stopping if we already have enough pairs
            if count >= p:
                return True
        return count >= p

    # Binary search boundaries: left is 0 and right is max diff in the array.
    left, right = 0, nums[-1] - nums[0]
    while left < right:
        mid = left + (right - left) // 2
        if can_form_pairs(mid):
            right = mid  # Try a smaller difference if possible
        else:
            left = mid + 1  # Increase the candidate difference
    return left

# Example usage:
print(minimizeMaxDifference([10,1,2,7,1,3], 2))  # Expected output: 1
← Back to All Questions