Maximum Product Difference Between Two Pairs

Easy

#1746Time: 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.

Algorithms

Sorting

Data structures

Array

Prompt

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 <= 10⁴
1 <= nums[i] <= 10⁴

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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]).

Walkthrough

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.

1import java.util.Arrays;2 3class Solution {4    public int maxProductDifference(int[] nums) {5        // Sort the array in ascending order.6        Arrays.sort(nums);7        8        int n = nums.length;9        10        // The two largest numbers are at the end of the sorted array.11        int largestProduct = nums[n - 1] * nums[n - 2];12        13        // The two smallest numbers are at the beginning of the sorted array.14        int smallestProduct = nums[0] * nums[1];15        16        // Return the difference.17        return largestProduct - smallestProduct;18    }19}

Complexity

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.

Trade-offs

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.

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.

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).

Walkthrough

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.

1class Solution {2    public int maxProductDifference(int[] nums) {3        // Initialize variables to track the two largest and two smallest numbers.4        int largest = Integer.MIN_VALUE;5        int secondLargest = Integer.MIN_VALUE;6        int smallest = Integer.MAX_VALUE;7        int secondSmallest = Integer.MAX_VALUE;8 9        // Iterate through the array once to find the four required numbers.10        for (int num : nums) {11            // Check for largest and second largest12            if (num > largest) {13                secondLargest = largest;14                largest = num;15            } else if (num > secondLargest) {16                secondLargest = num;17            }18 19            // Check for smallest and second smallest20            if (num < smallest) {21                secondSmallest = smallest;22                smallest = num;23            } else if (num < secondSmallest) {24                secondSmallest = num;25            }26        }27 28        // Calculate the maximum product difference.29        return (largest * secondLargest) - (smallest * secondSmallest);30    }31}

Complexity

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.

Trade-offs

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.

Solutions

Solution

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

1/** * @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 ; };

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

1class 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 ]; } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem