1913. Maximum Product Difference Between Two Pairs
Solved
Easy
Topics
Companies
Hint
The product difference between two pairs (a, b) and (c, d) is defined as (a * b) — (c * d).
For example, the product difference between (5, 6) and (2, 7) is (5 * 6) — (2 * 7) = 16.
Given an integer array nums, choose four distinct indices w, x, y, and z such that the product difference between pairs (nums[w], nums[x]) and (nums[y], nums[z]) is maximized.
Return the maximum such product difference.
Example 1:
Input: nums = [5,6,2,7,4]
Output: 34
Explanation: We can choose indices 1 and 3 for the first pair (6, 7) and indices 2 and 4 for the second pair (2, 4).
The product difference is (6 * 7) — (2 * 4) = 34.
Example 2:
Input: nums = [4,2,5,9,7,4,8]
Output: 64
Explanation: We can choose indices 3 and 6 for the first pair (9, 8) and indices 1 and 5 for the second pair (2, 4).
The product difference is (9 * 8) — (2 * 4) = 64.
Constraints:
4 <= nums.length <= 104
1 <= nums[i] <= 104
class Solution {
/** Time : O(nlog(n)) space : O(1)*/
public int maxProductDifference1(int[] nums) {
int n=nums.length,m=0;
//Arrays.sort(nums); Remarks : no in built functions
//quickSort(nums,0,n-1); Remarks : if we choose wrong pivot time will be O(n^2)
mergeSort(nums,0,n-1); //Remarks : we have to deal with space
return nums[n-1]*nums[n-2] - nums[0]*nums[1];
}
public int maxProductDifference(int[] nums) {
int fb=Integer.MIN_VALUE, sb=Integer.MIN_VALUE, fs=Integer.MAX_VALUE, ss=Integer.MAX_VALUE;
for(int i: nums){
if(i > fb){
sb=fb;
fb=i;
}else sb=Math.max(sb,i);
if(i<fs){
ss=fs;
fs=i;
}else ss=Math.min(ss,i);
}
return fb*sb - fs*ss;
}
/**Time :O(nlog(n)) Space : O(1)*/
public void quickSort(int[] nums, int l, int r){
if(l<r){
int pi=partition(nums,l, r);
quickSort(nums, l, pi-1);
quickSort(nums, pi+1,r);
}
}
public int partition(int[] nums, int l, int r){
int i=l-1, j=l;
while(j<r){
if(nums[j] < nums[r] ) swap(nums ,++i, j);
j++;
}
swap(nums,++i,r);
return i;
}
public void swap(int[] nums, int i, int j){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
/**Time :O(nlog(n)) Space :O(n) */
public void mergeSort(int[] nums, int l, int r){
if(l<r){
/**calcuate the mid of the array */
int mid = l+(r-l)/2;
/**continuesly divide the nums, smallest problems*/
mergeSort(nums, l, mid);
mergeSort(nums, mid+1, r);
/**merge the divided array*/
merge(nums, l , mid, r);
}
}
public void merge(int[] nums, int l, int mid, int r){
/**calculate the length of new sub arrays */
int n=mid-l+1 , m=r-mid , i=0, j=0, k=0;
/**create left and right subarrays */
int[] nArr=new int[n], mArr=new int[m];
/**copy the og array to sub arrays*/
while(i<n) nArr[i]=nums[l + i++];
while(j<m) mArr[j]=nums[mid+ 1 + j++];
/**merge left and right sub arrays by taking min*/
i=0;j=0;k=l;
while(i<n && j<m) nums[k++] = nArr[i]<=mArr[j] ? nArr[i++] : mArr[j++];
/**put the elements back to the subarray left overs */
while(i<n) nums[k++]=nArr[i++];
while(j<m) nums[k++]=mArr[j++];
}
}
/**
1913. Maximum Product Difference Between Two Pairs
Solved
Easy
Topics
Companies
Hint
The product difference between two pairs (a, b) and (c, d) is defined as (a * b) - (c * d).
For example, the product difference between (5, 6) and (2, 7) is (5 * 6) - (2 * 7) = 16.
Given an integer array nums, choose four distinct indices w, x, y, and z such that the product difference between pairs (nums[w], nums[x]) and (nums[y], nums[z]) is maximized.
Return the maximum such product difference.
Example 1:
Input: nums = [5,6,2,7,4]
Output: 34
Explanation: We can choose indices 1 and 3 for the first pair (6, 7) and indices 2 and 4 for the second pair (2, 4).
The product difference is (6 * 7) - (2 * 4) = 34.
Example 2:
Input: nums = [4,2,5,9,7,4,8]
Output: 64
Explanation: We can choose indices 3 and 6 for the first pair (9, 8) and indices 1 and 5 for the second pair (2, 4).
The product difference is (9 * 8) - (2 * 4) = 64.
Constraints:
4 <= nums.length <= 104
1 <= nums[i] <= 104
*/
