Maximum Product Difference Between Two Pairs solution and explanation
9 more videos on this problem
Maximum Product Difference Between Two - Leetcode 1913 - PythonNeetCodeIO · 10:55 · 6K views
Maximum Product Difference Between Two Pairs | 2 Simple Approaches | Leetcode-1913codestorywithMIK · 9:46 · 4K views
Maximum Product Difference Between Two Pairs | LeetCode 1913 | EnglishCodeClips with Abhishek Ranjan · 6:19 · 1K views
1913. Maximum Product Difference Between Two Pairs (Leetcode Easy)Programming Live with Larry · 3:55 · 577 views
1913. Maximum Product Difference Between Two Pairs || Java || LeetcodeCoding Sphere · 11:28 · 415 views
Leetcode | 1913. Maximum Product Difference Between Two Pairs | Easy | Java Solution [2 Methods]Developer Docs · 6:08 · 395 views
1913. Maximum Product Difference Between Two Pairs - LeetCode JavascriptBecoming A Better Dev (with David) · 13:21 · 224 views
1913. Maximum Product Difference Between Two Pairs with JavaScirpt | Leetcode with JavascriptArsalan Ahmed · 6:42 · 82 views
1913 Maximum Product Difference Between Two PairsMath Geeks · 2:01 · 68 views
Maximum Product Difference Between Two Pairs || LEETCODE EASY (1913)DebugwithAnjali · 16:17 · 55 views
The problem
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 <= 1041 <= nums[i] <= 104
Approach overview
Problem Overview: You receive an integer array nums. The task is to choose four distinct elements and compute the maximum value of (a * b) - (c * d). To maximize this expression, you want the product of the two largest numbers and subtract the product of the two smallest numbers.
Approach 1: Sort and Pick Extremes (Time: O(n log n), Space: O(1) or O(log n) depending on sort)
Sorting the array makes the structure obvious. After sorting, the two largest values sit at the end of the array and the two smallest values at the beginning. Compute (nums[n-1] * nums[n-2]) - (nums[0] * nums[1]). This works because any other pair would reduce the first product or increase the second one, lowering the final difference. The implementation is short and reliable, which makes it a good baseline solution when using sorting utilities already available in your language.
The algorithm performs a full sort of the array, which costs O(n log n) time. Space usage depends on the sorting implementation but is typically O(1) for in-place sorts or O(log n) due to recursion. If the array is already sorted or you are solving multiple queries on the same sorted data, this approach becomes even more convenient.
Approach 2: Linear Pass with Four Variables (Time: O(n), Space: O(1))
A more optimal solution avoids sorting entirely. Instead, track the two largest and two smallest numbers while scanning the array once. Maintain variables such as max1, max2, min1, and min2. During each iteration, update these values based on comparisons with the current element.
At the end of the scan, compute the result using (max1 * max2) - (min1 * min2). The key insight is that only four numbers influence the final answer: the top two and bottom two values in the array. Everything else is irrelevant. This approach leverages a single pass over the array, making it strictly faster than sorting for large inputs.
This method runs in O(n) time and uses constant O(1) extra space. It’s also straightforward to implement in languages like C++, Java, or Python with simple conditional checks.
Recommended for interviews: The linear pass with four variables is the solution interviewers typically expect. Sorting demonstrates the correct observation about extremes, but the O(n) scan shows stronger algorithmic thinking and better control over array traversal. Mention the sorting approach first if discussing tradeoffs, then implement the linear scan as the optimal answer.
Approach 1: Sort and Pick Extremes
This approach involves sorting the array and then selecting the appropriate numbers to form two pairs. The largest two numbers should form one pair to maximize the product, and the smallest two numbers should form the other pair to minimize the product. This ensures that the product difference is as large as possible:
1. Sort the array nums.
2. Select the two largest numbers for (a, b) and the two smallest numbers for (c, d).
3. Compute the product difference as (a * b) - (c * d).
def maxProductDifference(nums):
nums.sort()
return nums[-1] * nums[-2] - nums[0] * nums[1]
nums = [4, 2, 5, 9, 7, 4, 8]
print(maxProductDifference(nums))import java.util.Arrays;
public class MaxProdDifference {
public static int maxProductDifference(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
return nums[n-1] * nums[n-2] - nums[0] * nums[1];
}
public static void main(String[] args) {
int[] nums = {4, 2, 5, 9, 7, 4, 8};
System.out.println(maxProductDifference(nums));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int maxProductDifference(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
int n = nums.size();
return nums[n-1] * nums[n-2] - nums[0] * nums[1];
}
int main() {
std::vector<int> nums = {4, 2, 5, 9, 7, 4, 8};
std::cout << maxProductDifference(nums) << std::endl;
return 0;
}function maxProductDifference(nums) {
nums.sort((a, b) => a - b);
const n = nums.length;
return nums[n - 1] * nums[n - 2] - nums[0] * nums[1];
}
const nums = [4, 2, 5, 9, 7, 4, 8];
console.log(maxProductDifference(nums));#include <stdio.h>
#include <stdlib.h>
int cmpfunc(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int maxProductDifference(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), cmpfunc);
int maxProd = nums[numsSize - 1] * nums[numsSize - 2];
int minProd = nums[0] * nums[1];
return maxProd - minProd;
}
int main() {
int nums[] = {4, 2, 5, 9, 7, 4, 8};
int result = maxProductDifference(nums, 7);
printf("%d\n", result);
return 0;
}using System;
class MaxProdDifference {
static int MaxProductDifference(int[] nums) {
Array.Sort(nums);
int n = nums.Length;
return nums[n - 1] * nums[n - 2] - nums[0] * nums[1];
}
static void Main() {
int[] nums = { 4, 2, 5, 9, 7, 4, 8 };
Console.WriteLine(MaxProductDifference(nums));
}
}In this Python solution, the input list nums is sorted, and the product difference is computed by using indices to access the required elements.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1), aside from input storage.
Approach 2: Linear Pass with Four Variables
Instead of sorting, we can solve the problem in linear time by keeping track of the four numbers we need: the two largest numbers and the two smallest numbers:
1. Initialize variables to hold the minimum two and maximum two values seen so far.
2. Iterate through the array, updating these variables accordingly.
3. Calculate the product difference with the two largest and two smallest values obtained.
def maxProductDifference(nums):
max1, max2 = 0, 0
min1, min2 = float('inf'), float('inf')
for num in nums:
if num > max1:
max2 = max1
max1 = num
elif num > max2:
max2 = num
if num < min1:
min2 = min1
min1 = num
elif num < min2:
min2 = num
return max1 * max2 - min1 * min2
nums = [4, 2, 5, 9, 7, 4, 8]
print(maxProductDifference(nums))public class MaxProdDifference {
public static int maxProductDifference(int[] nums) {
int max1 = 0, max2 = 0, min1 = 10001, min2 = 10001;
for (int num : nums) {
if (num > max1) {
max2 = max1;
max1 = num;
} else if (num > max2) {
max2 = num;
}
if (num < min1) {
min2 = min1;
min1 = num;
} else if (num < min2) {
min2 = num;
}
}
return max1 * max2 - min1 * min2;
}
public static void main(String[] args) {
int[] nums = {4, 2, 5, 9, 7, 4, 8};
System.out.println(maxProductDifference(nums));
}
}#include <iostream>
#include <vector>
int maxProductDifference(std::vector<int>& nums) {
int max1 = 0, max2 = 0, min1 = 10001, min2 = 10001;
for (int num : nums) {
if (num > max1) {
max2 = max1;
max1 = num;
} else if (num > max2) {
max2 = num;
}
if (num < min1) {
min2 = min1;
min1 = num;
} else if (num < min2) {
min2 = num;
}
}
return max1 * max2 - min1 * min2;
}
int main() {
std::vector<int> nums = {4, 2, 5, 9, 7, 4, 8};
std::cout << maxProductDifference(nums) << std::endl;
return 0;
}function maxProductDifference(nums) {
let max1 = 0, max2 = 0, min1 = Infinity, min2 = Infinity;
for (let num of nums) {
if (num > max1) {
max2 = max1;
max1 = num;
} else if (num > max2) {
max2 = num;
}
if (num < min1) {
min2 = min1;
min1 = num;
} else if (num < min2) {
min2 = num;
}
}
return (max1 * max2) - (min1 * min2);
}
const nums = [4, 2, 5, 9, 7, 4, 8];
console.log(maxProductDifference(nums));#include <stdio.h>
int maxProductDifference(int* nums, int numsSize) {
int max1 = 0, max2 = 0, min1 = 10001, min2 = 10001;
for (int i = 0; i < numsSize; i++) {
if (nums[i] > max1) {
max2 = max1;
max1 = nums[i];
} else if (nums[i] > max2) {
max2 = nums[i];
}
if (nums[i] < min1) {
min2 = min1;
min1 = nums[i];
} else if (nums[i] < min2) {
min2 = nums[i];
}
}
return (max1 * max2) - (min1 * min2);
}
int main() {
int nums[] = {4, 2, 5, 9, 7, 4, 8};
int result = maxProductDifference(nums, 7);
printf("%d\n", result);
return 0;
}using System;
class MaxProdDifference {
static int MaxProductDifference(int[] nums) {
int max1 = 0, max2 = 0, min1 = 10001, min2 = 10001;
foreach (int num in nums) {
if (num > max1) {
max2 = max1;
max1 = num;
} else if (num > max2) {
max2 = num;
}
if (num < min1) {
min2 = min1;
min1 = num;
} else if (num < min2) {
min2 = num;
}
}
return max1 * max2 - min1 * min2;
}
static void Main() {
int[] nums = { 4, 2, 5, 9, 7, 4, 8 };
Console.WriteLine(MaxProductDifference(nums));
}
}This Python solution uses four variables to determine the largest and smallest pairs in a single, linear pass, thereby avoiding the overhead of sorting.
Time Complexity: O(n) for a single traversal of the array.
Space Complexity: O(1) with only fixed additional space needed.
Approach 3: Default Approach
func maxProductDifference(nums []int) int {
sort.Ints(nums)
n := len(nums)
return nums[n-1]*nums[n-2] - nums[0]*nums[1]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sort and Pick Extremes | Time Complexity: O(n log n) due to sorting. Space Complexity: O(1), aside from input storage. |
| Linear Pass with Four Variables | Time Complexity: O(n) for a single traversal of the array. Space Complexity: O(1) with only fixed additional space needed. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort and Pick Extremes | O(n log n) | O(1) to O(log n) | When simplicity matters or the array is already sorted |
| Linear Pass with Four Variables | O(n) | O(1) | Best general solution when you want optimal time without sorting |
Frequently asked questions
Is Maximum Product Difference Between Two Pairs easy or hard?
Maximum Product Difference Between Two Pairs is classified as an Easy problem on LeetCode with a high acceptance rate. The challenge focuses on recognizing that only the two largest and two smallest numbers affect the final result.
Maximum Product Difference Between Two Pairs Python/Java solution
Python and Java implementations typically follow the same logic: either sort the array and compute the result from the extremes, or perform a single pass tracking the two largest and two smallest values. The linear scan solution runs in O(n) time and uses constant memory.
How to solve Maximum Product Difference Between Two Pairs in O(n)?
Scan the array once while maintaining four variables: the two largest numbers and the two smallest numbers seen so far. Update them during each iteration using comparisons. After the loop, compute (max1 * max2) - (min1 * min2) to get the maximum product difference.
What is the best approach for Maximum Product Difference Between Two Pairs?
The optimal approach is a single linear scan that tracks the two largest and two smallest numbers. After one pass, compute (max1 * max2) - (min1 * min2). This method runs in O(n) time and uses O(1) extra space, making it more efficient than sorting.
Is Maximum Product Difference Between Two Pairs asked at Google/Amazon/Meta?
This problem represents a common array scanning pattern often used in coding interviews at companies like Amazon and other product companies. While the exact question may vary, identifying extreme values in a single pass is a frequent interview concept.
What data structure is used in Maximum Product Difference Between Two Pairs?
The problem mainly uses arrays and simple variable tracking. The optimal solution does not require extra data structures; it only maintains four integer variables while iterating through the array.
What is the time complexity of Maximum Product Difference Between Two Pairs?
The optimal solution runs in O(n) time using a single pass to track the two largest and two smallest values. A simpler alternative sorts the array first, which takes O(n log n) time. Both approaches use constant extra space.