2616. Minimize the Maximum Difference of Pairs
Problem¶
You are given a 0-indexed integer array nums and an integer p. Find p pairs of indices of nums such that the maximum difference amongst all the pairs is minimized. Also, ensure no index appears more than once amongst the p pairs.
Note that for a pair of elements at the index i and j, the difference of this pair is |nums[i] - nums[j]|, where |x| represents the absolute value of x.
Return the minimum maximum difference among all p pairs. We define the maximum of an empty set to be zero.
Example 1:
Input: nums = [10,1,2,7,1,3], p = 2
Output: 1
Explanation: The first pair is formed from the indices 1 and 4, and the second pair is formed from the indices 2 and 5.
The maximum difference is max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1. Therefore, we return 1.
Example 2:
Input: nums = [4,2,1,2], p = 1
Output: 0
Explanation: Let the indices 1 and 3 form a pair. The difference of that pair is |2 - 2| = 0, which is the minimum we can attain.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 1090 <= p <= (nums.length)/2
Solve¶
class Solution:
def minimizeMax(self, nums: List[int], p: int) -> int:
nums.sort()
# Choosing pair base on sorted number, get mimimal number
# (1,2) (3,4) (...) (2p-1, 2p)
def greedy(self, nums):
def helper(x,y):
return nums[y] - nums[x]
minimize = None
for i in range(0,len(nums), 2):
if minimize is None:
minimize = helper(i, i+1)
elif minimize > helper(i, i+1):
minimize = helper(i, i+1)
return minimize
# We can chosing number base on their distinct, from lowest to largest
# Keeping track of all added pair to make sure we adding not visided number
def smarter(self, nums)
def helper(x,y):
return nums[y] - nums[x]
# By sorting, we rounded down possible pair to choose to adj number only
# by example [1,2,3,4] right next to each other
# -> We can only choing [1,2] [3,4] or [2,3] [1,4]. But because of sorting
# [1,4] > any of ([1,2] [2,3] [3,4])
# -> We won't using any pair that isn't adj each other
possible_pair = []
for i in range(0, len(num)):
pair = [i, i+1]
possible_pair.append( pair )
def sortkey(x):
return helper(*x)
possible_pair.sort(key = sortkey)
# Checking and pushing each pair from the lowest to highest isn't possible
# As we need to take care a lot of vairable stage
"""queue = []
while queue:
pair, diff = possible_pair.pop()
visited_number
queue.append(visited_number)"""
# Instead, we can try to using some dynamic programing and maximize the
# pair that we can choose step by step in avaiable possible_pair
max_pair = []
for x, y in possible_pair:
Created : August 16, 2023