Maximum Product Difference Between Two Pairs

LeetCode 1913: Maximum Product Difference Between Two Pairs asks you to pick two pairs of numbers from an array and maximize the difference between their products. It is one of those easy problems that teaches you a useful pattern: you do not always need to sort an array to find its extreme values.

The problem

You are given an integer array nums of length 4 or more. The product difference between two pairs (a, b) and (c, d) is defined as (a * b) - (c * d). You need to choose four indices w, x, y, z (all distinct) and return the maximum product difference between pairs (nums[w], nums[x]) and (nums[y], nums[z]).

For example, given nums = [5, 6, 2, 7, 4], the maximum product difference is (7 * 6) - (2 * 4) = 42 - 8 = 34.

The key insight is that to maximize (a * b) - (c * d), you want a * b to be as large as possible and c * d to be as small as possible. That means you need the two largest numbers for the first pair and the two smallest numbers for the second pair.

The approach

There are two clean ways to solve this.

Option 1: Sort the array. After sorting, the two smallest values are at the front and the two largest are at the end. Grab them and compute the answer. This costs O(n log n) time.

Option 2: One-pass tracking. Walk through the array once, maintaining four variables: the two largest values (max1, max2) and the two smallest values (min1, min2). At each element, update these trackers. This runs in O(n) time and O(1) space.

Both approaches are correct, but the one-pass version is more efficient and demonstrates a pattern you will reuse in problems like finding the top-k elements, tracking running extremes, or computing products of array values.

Here is the one-pass solution:

def max_product_difference(nums: list[int]) -> int:
    max1 = max2 = float('-inf')
    min1 = min2 = 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)

Let's walk through exactly how this works on nums = [5, 6, 2, 7, 4].

Complexity analysis

Time: O(n). A single pass through the array. Each element triggers a constant number of comparisons and assignments.

Space: O(1). Four tracking variables regardless of input size.

If you used sorting instead:

Both are fine for this problem's constraints, but the one-pass version is strictly better and shows you understand how to avoid unnecessary work.

The Building Blocks

This problem breaks down into one core building block: tracking multiple extremes in a single pass.

Two-largest / two-smallest tracking

The idea is to maintain a small set of extreme values as you iterate. When a new element arrives, you check whether it displaces the current top (or bottom) values and shift them down accordingly. This is the same logic behind finding the third maximum, the k closest points, or the top-k frequent elements (when k is small and fixed).

The template:

max1 = max2 = float('-inf')
for num in nums:
    if num >= max1:
        max2 = max1
        max1 = num
    elif num > max2:
        max2 = num

This pattern generalizes: if you need the top 3, add a max3 variable. For arbitrary k, switch to a heap. But for small fixed k (like 2), inline variables are faster and simpler.

Edge cases to watch for

• All elements equal, like [3, 3, 3, 3]. Both products are 3 * 3 = 9, so the difference is 0.
• Minimum length array [a, b, c, d]. You have exactly four elements, so the two largest and two smallest are simply the sorted array's endpoints.
• Large values. The constraints say values can be up to 10^4 and the array can have up to 10^5 elements. Products fit comfortably in a 32-bit integer, so overflow is not a concern in Python (or most languages with 64-bit integers).
• Duplicates. [1, 1, 1, 10, 10] gives (10 * 10) - (1 * 1) = 99. The tracking logic handles equal values correctly because of the >= and <= comparisons.

From understanding to recall

You have read through the one-pass solution and it makes sense. But can you write it from scratch? The tricky part is the update logic: when a new value is larger than max1, you need to demote max1 to max2 before overwriting it. Miss that step and you lose the second-largest value entirely.

That is the kind of subtle detail that spaced repetition is designed to lock in. You practice the two-largest tracking template a few times at increasing intervals. After a couple of cycles, the demotion step becomes automatic. Then when you see a problem that asks for the top 2 or bottom 2 values, you write the code from muscle memory instead of re-deriving it under pressure.

Related posts

• Contains Duplicate - Another easy array problem that introduces a foundational pattern (the seen-set) you will reuse everywhere
• Kth Largest Element - When tracking the top k values with fixed variables does not scale, a heap takes over
• Best Time to Buy and Sell Stock - Another single-pass problem built on tracking a running extreme (the minimum price so far)