source: https://leetcode.com/problems/minimize-the-maximum-difference-of-pairs/
Table of Contents
Minimize the Maximum Difference of Pairs
You are given a 0-indexed integer array nums and an integer p. Find p pairs of indices of nums to minimize the maximum difference amongst all the pairs. 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 <= 105
- 0 <= nums[i] <= 109
- 0 <= p <= (nums.length)/2
Solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
class Solution { public int minimizeMax(int[] nums, int p) { //sorting the Array is required to limit the comparison only to the adjacent numbers Arrays.sort(nums); int lo = 0; int hi = nums[nums.length-1]-nums[0]; while(lo<hi){ int mid = lo + (hi-lo)/2; if(isFeasible(nums, p, mid)){ hi = mid; }else { lo = mid+1; } } return lo; } //see if the count of pairs having difference >= target is greater than or equals to p private boolean isFeasible(int[] nums, int p, int target){ int i = 0; int count = 0; while(i < nums.length-1){ if(Math.abs(nums[i]- nums[i+1]) <= target){ count++; i++; } i++; if(count>=p){ return true; } } return false; } //Memory Limit Exceeded // public int minimizeMax(int[] nums, int p) { // //sorting the Array is required to limit the comparison only to the adjacent numbers // Arrays.sort(nums); // Integer[][] memo = new Integer[p+1][nums.length+1]; // return dfs(nums, p, 0, memo); // } // private int dfs(int[] nums, int p, int i, Integer[][] memo){ // if(p==0) // return 0; // if(i>= nums.length-1) // return Integer.MAX_VALUE; // if(memo[p][i]!=null) // return memo[p][i]; // //either you can choose a number at the current index and the next number to be part of the pair // int choose = Math.max(Math.abs(nums[i] - nums[i+1]), dfs(nums, p-1, i+2, memo)); // //not choose a number and move the next index // int notChoose = dfs(nums, p, i+1, memo); // memo[p][i] = Math.min(choose, notChoose); // return memo[p][i]; // } } |