<p>The <strong>product difference</strong> between two pairs <code>(a, b)</code> and <code>(c, d)</code> is defined as <code>(a * b) - (c * d)</code>.</p>

<ul>
	<li>For example, the product difference between <code>(5, 6)</code> and <code>(2, 7)</code> is <code>(5 * 6) - (2 * 7) = 16</code>.</li>
</ul>

<p>Given an integer array <code>nums</code>, choose four <strong>distinct</strong> indices <code>w</code>, <code>x</code>, <code>y</code>, and <code>z</code> such that the <strong>product difference</strong> between pairs <code>(nums[w], nums[x])</code> and <code>(nums[y], nums[z])</code> is <strong>maximized</strong>.</p>

<p>Return <em>the <strong>maximum</strong> such product difference</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [5,6,2,7,4]
<strong>Output:</strong> 34
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [4,2,5,9,7,4,8]
<strong>Output:</strong> 64
<strong>Explanation:</strong> 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.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>4 &lt;= nums.length &lt;= 10<sup>4</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>
</ul>
class Solution {
public:
/*
info:
    - product difference: (a * b) - (c * d) = k
    - distinct: a != b != c != d
    - maximizum difference: max(k)

    design:
    1.
    n = number of value in nums;
    time complexity : f(n) <= O(n*log(n)) / space complexity : f(n) <= O(n)
      steps: arr.sort() -> (arr[n -1] * arr[n-2]) -  (arr[0] * arr[1])
    
    2. 
    time complexity : f(n) <= O(n) / space complexity : f(n) <= O(1)
      steps: loop in arr -> find first_max and second_max -> find first_min and sec_min
      as you loop make sure that first_max != sec_min and first_min != sec_min
*/


int maxProductDifference(std::vector<int>& nums) {
    if (nums.size() < 4) {
        // Not enough elements to find two distinct max and min pairs
        return 0;
    }

    int first_max = std::numeric_limits<int>::min();
    int second_max = std::numeric_limits<int>::min();
    int first_min = std::numeric_limits<int>::max();
    int second_min = std::numeric_limits<int>::max();

    for (int num : nums) {
        // Update maximum values
        if (num > second_max) {
            if (num > first_max){
                second_max = first_max;
                first_max = num;
            } else {
                second_max = num;
            }
        }

        // Update minimum values
        if (num < second_min) {
            if(num < first_min){
                second_min = first_min;
                first_min = num;
            } else{
                second_min = num;
            }
        }
    }

    // Ensure that second_max and second_min are valid
    if (second_max == std::numeric_limits<int>::min() || 
        second_min == std::numeric_limits<int>::max()) {
        return 0;
    }

    // Use long long to avoid overflow in multiplication
    long long maxProduct = static_cast<long long>(first_max) * second_max;
    long long minProduct = static_cast<long long>(first_min) * second_min;

    return static_cast<int>(maxProduct - minProduct);
    }
};
23200