Maximum Difference by Remapping a Digit

main.md

Question

Approach

I start by sorting the array nums because closer numbers are more likely to form pairs with smaller differences. Then I binary search on the minimum maximum allowed difference (let’s call it maxDiff). For each maxDiff candidate, I greedily count how many disjoint pairs I can form such that each pair has a difference ≤ maxDiff. If I can form at least p such pairs, I reduce the search space. Otherwise, I increase it.

Implementation

class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:
        nums.sort()

        def can_form_pairs(max_diff):
            count = 0
            i = 0
            while i < len(nums) - 1:
                if nums[i + 1] - nums[i] <= max_diff:
                    count += 1
                    i += 2 
                else:
                    i += 1
            return count >= p

        left, right = 0, nums[-1] - nums[0]
        while left < right:
            mid = (left + right) // 2
            if can_form_pairs(mid):
                right = mid
            else:
                left = mid + 1
        return left

Complexities

• Time: O(n logn)
• Space: O(1)