Maximum Product Difference Between Two Pairs

Maximum Product Difference Between Two Pairs - Problem

Array Sorting Easy

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) = 30 - 14 = 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [5,6,2,7,1,4]

› Output: 40

💡 Note: Choose indices (1,3) for pair (6,7) and (2,4) for pair (2,1). Product difference is (6×7) - (2×1) = 42 - 2 = 40.

Example 2 — Small Array

$ Input: nums = [4,2,5,9]

› Output: 34

💡 Note: Choose indices (2,3) for pair (5,9) and (0,1) for pair (4,2). Product difference is (5×9) - (4×2) = 45 - 8 = 37. Wait, let's try (3,2) and (1,0): (9×5) - (2×4) = 45 - 8 = 37. Actually best is (9×5) - (2×4) = 37.

Example 3 — Negative Numbers

$ Input: nums = [-1,-2,-3,-4]

› Output: 2

💡 Note: Choose indices (0,1) for pair (-1,-2) and (2,3) for pair (-3,-4). Product difference is ((-1)×(-2)) - ((-3)×(-4)) = 2 - 12 = -10. Actually best is ((-3)×(-4)) - ((-1)×(-2)) = 12 - 2 = 10.

Constraints

4 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array with at least 4 elements

Process

Find two largest and two smallest elements

Output

Maximum product difference

Key Takeaway

🎯 Key Insight: Maximum difference always comes from (largest × second largest) - (smallest × second smallest)

Asked in

a Amazon 25 M Microsoft 18 G Google 12

The key insight is that maximum product difference comes from multiplying the two largest numbers and subtracting the product of the two smallest numbers. Best approach is the one-pass solution that tracks extremes while scanning. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ One Pass (Optimal)	O(n)	O(1)	Find two largest and two smallest elements in single pass
Sort First	O(n log n)	O(1)	Sort array and pick two largest and two smallest elements
Brute Force	O(n⁴)	O(1)	Try all possible combinations of four distinct indices

One Pass (Optimal) — Algorithm Steps

Initialize variables for largest and smallest pairs
Scan array once, updating maximums and minimums
Calculate product difference using found extremes

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set up variables to track two largest and smallest

Scan Once

Update extremes as we encounter each element

Calculate

Use tracked extremes to get maximum difference

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int* nums, int numsSize) {
    int max1 = INT_MIN, max2 = INT_MIN;
    int min1 = INT_MAX, min2 = INT_MAX;
    
    for (int i = 0; i < numsSize; i++) {
        int num = nums[i];
        
        // Update maximums
        if (num > max1) {
            max2 = max1;
            max1 = num;
        } else if (num > max2) {
            max2 = num;
        }
        
        // Update minimums
        if (num < min1) {
            min2 = min1;
            min1 = num;
        } else if (num < min2) {
            min2 = num;
        }
    }
    
    return max1 * max2 - min1 * min2;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int size = 0;
    char* token = strtok(line, "[,]");
    
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array to find extremes

✓ Linear Growth

Space Complexity

O(1)

Only constant variables to track extremes

✓ Linear Space

23.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

One Pass (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler