# Maximum Product Difference Between Two Pairs
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-product-difference-between-two-pairs)
Canonical: https://scaleengineer.com/dsa/problems/maximum-product-difference-between-two-pairs
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## 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 <= 104`
* `1 <= nums[i] <= 104`

# Approaches
## Sorting the Array
The problem asks to maximize the expression `(a * b) - (c * d)`. To achieve this, we need to maximize the product `a * b` and minimize the product `c * d`. Since all numbers in the input array are positive, the product of two numbers is maximized by choosing the two largest numbers available, and minimized by choosing the two smallest numbers.

This insight simplifies the problem to finding the two largest and two smallest elements in the array. A straightforward way to do this is by sorting the array.
**Time:** O(n log n), where n is the number of elements in the array. The dominant operation is sorting the array, which typically takes O(n log n) time. · **Space:** O(log n) to O(n). The space complexity depends on the implementation of the sorting algorithm. In Java, `Arrays.sort()` for primitive types uses a variant of Quicksort, which has an average space complexity of O(log n) for the recursion stack.
**Pros:** Simple to understand and implement.; Correctly finds the two largest and two smallest elements.
**Cons:** Not the most efficient solution in terms of time complexity. Sorting the entire array is more work than necessary, as we only need the four extreme values.
### Explanation
If we sort the array `nums` in non-decreasing order, the two smallest elements will be at the beginning of the array, and the two largest elements will be at the end.

```java
import java.util.Arrays;

class Solution {
    public int maxProductDifference(int[] nums) {
        // Sort the array in ascending order.
        Arrays.sort(nums);
        
        int n = nums.length;
        
        // The two largest numbers are at the end of the sorted array.
        int largestProduct = nums[n - 1] * nums[n - 2];
        
        // The two smallest numbers are at the beginning of the sorted array.
        int smallestProduct = nums[0] * nums[1];
        
        // Return the difference.
        return largestProduct - smallestProduct;
    }
}
```
### Algorithm
- Sort the input array `nums` in ascending order.
- Let `n` be the length of the array.
- The two smallest numbers are `nums[0]` and `nums[1]`.
- The two largest numbers are `nums[n-1]` and `nums[n-2]`.
- The maximum product difference is calculated as `(nums[n-1] * nums[n-2]) - (nums[0] * nums[1])`.

## Single Pass Iteration
Instead of sorting the entire array, we can find the two largest and two smallest numbers by iterating through the array just once. This avoids the `O(n log n)` time complexity of sorting and achieves a more optimal linear time solution.
**Time:** O(n), where n is the number of elements. We iterate through the array of n elements exactly once, and each step inside the loop takes constant time. · **Space:** O(1). We only use a fixed number of variables (`largest`, `secondLargest`, `smallest`, `secondSmallest`) regardless of the input array size.
**Pros:** Highly efficient with linear time complexity.; Optimal solution as we must look at each element at least once.; Minimal space usage.
**Cons:** The logic inside the loop is slightly more complex than the sorting approach, requiring careful handling of comparisons and updates.
### Explanation
We can maintain four variables to keep track of the two largest and two smallest numbers encountered so far during a single traversal of the array.

```java
class Solution {
    public int maxProductDifference(int[] nums) {
        // Initialize variables to track the two largest and two smallest numbers.
        int largest = Integer.MIN_VALUE;
        int secondLargest = Integer.MIN_VALUE;
        int smallest = Integer.MAX_VALUE;
        int secondSmallest = Integer.MAX_VALUE;

        // Iterate through the array once to find the four required numbers.
        for (int num : nums) {
            // Check for largest and second largest
            if (num > largest) {
                secondLargest = largest;
                largest = num;
            } else if (num > secondLargest) {
                secondLargest = num;
            }

            // Check for smallest and second smallest
            if (num < smallest) {
                secondSmallest = smallest;
                smallest = num;
            } else if (num < secondSmallest) {
                secondSmallest = num;
            }
        }

        // Calculate the maximum product difference.
        return (largest * secondLargest) - (smallest * secondSmallest);
    }
}
```
### Algorithm
- Initialize four variables: `largest`, `secondLargest`, `smallest`, and `secondSmallest` with appropriate sentinel values (e.g., `Integer.MIN_VALUE` and `Integer.MAX_VALUE`).
- Iterate through each number `num` in the `nums` array.
- For each `num`, update the four variables:
  - If `num` is greater than `largest`, update both `largest` and `secondLargest`.
  - Else if `num` is greater than `secondLargest`, update `secondLargest`.
  - If `num` is smaller than `smallest`, update both `smallest` and `secondSmallest`.
  - Else if `num` is smaller than `secondSmallest`, update `secondSmallest`.
- After the loop, calculate the result as `(largest * secondLargest) - (smallest * secondSmallest)`.

# Solutions
### Java

```java
class Solution { public int maxProductDifference ( int [] nums ) { Arrays . sort ( nums ); int n = nums . length ; return nums [ n - 1 ] * nums [ n - 2 ] - nums [ 0 ] * nums [ 1 ]; } }
```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number} */ var maxProductDifference = function ( nums ) { nums . sort (( a , b ) => a - b ); let n = nums . length ; let ans = nums [ n - 1 ] * nums [ n - 2 ] - nums [ 0 ] * nums [ 1 ]; return ans ; };
```

### Python

```python
class Solution : def maxProductDifference ( self , nums : List [ int ]) -> int : nums . sort () return nums [ - 1 ] * nums [ - 2 ] - nums [ 0 ] * nums [ 1 ]
```

### CPP

```cpp
class Solution { public: int maxProductDifference ( vector < int >& nums ) { sort ( nums . begin (), nums . end ()); int n = nums . size (); return nums [ n - 1 ] * nums [ n - 2 ] - nums [ 0 ] * nums [ 1 ]; } };
```