LeetCode Problem 1913

Difficulty: 🟢 Easy
Topics: Array, Sorting

Solution

Problem Understanding

This problem asks us to find the maximum product difference between two pairs of numbers from a given array. Specifically, given an array nums, we need to select four distinct indices w, x, y, z to form two pairs (nums[w], nums[x]) and (nums[y], nums[z]). The goal is to maximize the expression (nums[w] * nums[x]) - (nums[y] * nums[z]).

The input array contains integers ranging from 1 to 10,000 and has at least four elements. These constraints guarantee that a valid solution always exists. The output is a single integer representing the largest product difference possible.

Key observations include:

1. Since we want to maximize (a * b) - (c * d), the first pair (a, b) should consist of the two largest numbers, while the second pair (c, d) should consist of the two smallest numbers in the array.
2. All numbers are positive, so no special handling for negative numbers is required.
3. Edge cases like arrays where multiple numbers are equal, or minimal length arrays (length = 4), must be handled correctly, but the logic above naturally works.

Approaches

The brute-force approach would involve generating all possible combinations of four distinct indices, forming pairs, and computing the product differences. While this guarantees correctness, it is highly inefficient because the number of ways to pick four indices is C(n, 4) = n*(n-1)*(n-2)*(n-3)/24. For large arrays (n = 10^4), this is computationally infeasible.

The optimal approach leverages the insight that only the two largest and two smallest numbers matter. By sorting the array, we can immediately identify the two largest numbers at the end and the two smallest numbers at the start. The maximum product difference is then simply (max1 * max2) - (min1 * min2).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^4)	O(1)	Enumerates all 4-element combinations and computes differences
Optimal	O(n log n)	O(1)	Sorts the array to pick largest and smallest pairs directly

Algorithm Walkthrough

1. Sort the array in ascending order. Sorting allows us to efficiently identify the two smallest and two largest elements.
2. Select the two largest numbers from the end of the array. Denote them as max1 and max2. These form the pair that will contribute positively to the product difference.
3. Select the two smallest numbers from the start of the array. Denote them as min1 and min2. These form the pair whose product will be subtracted.
4. Compute the maximum product difference using the formula (max1 * max2) - (min1 * min2).
5. Return the computed value.

Why it works: Because all numbers are positive, multiplying the two largest numbers produces the maximum positive contribution, and multiplying the two smallest numbers produces the minimum subtraction. No other combination can produce a larger difference, so this strategy guarantees the correct maximum. The problem asks us to select four distinct elements from an integer array nums and split them into two pairs. We then compute the product of each pair and take the difference between these two products. Specifically, if we choose pairs (a, b) and (c, d), the value we compute is (a * b) - (c * d). The goal is to maximize this value over all possible choices of four distinct indices.

In simpler terms, we want to pick two numbers to form a large product and two other numbers to form a small product, such that the difference between these two products is as large as possible.

The input is an array of integers nums, where each element is positive and the length is between 4 and 10,000. The output is a single integer representing the maximum achievable product difference.

The constraints indicate that a brute-force combinational approach is infeasible due to the potential number of quadruples. The values are also bounded and positive, which simplifies reasoning since ordering by magnitude is meaningful.

Important edge cases include arrays where all values are equal, arrays with minimal length exactly 4, and arrays where the maximum values are clustered or duplicated. The positivity constraint ensures we do not need to consider sign interactions.

Approaches

Brute Force Idea

A brute-force solution would involve trying every possible selection of four distinct indices, then partitioning them into two pairs in all possible ways. For each quadruple, we compute the product difference and track the maximum.

This approach is correct because it explicitly evaluates all valid configurations. However, it is computationally infeasible. The number of ways to choose four elements from n is O(n^4), and for each selection, we may consider multiple pairings, making it even worse.

Key Insight

To maximize (a * b) - (c * d), we want to maximize a * b and simultaneously minimize c * d. Since all numbers are positive, the maximum product always comes from the two largest numbers, and the minimum product comes from the two smallest numbers.

This reduces the problem to a simple sorting-based selection: after sorting the array, the answer is:

• Largest product: product of the two largest elements
• Smallest product: product of the two smallest elements

Thus, the answer is:

(max1 * max2) - (min1 * min2)

Comparison Table

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^4)	O(1)	Tries all quadruples and pairings
Optimal	O(n log n)	O(1) or O(n)	Sort and use extremes

Algorithm Walkthrough

1. First, we sort the array in ascending order. This step is crucial because it allows us to easily identify the smallest and largest elements. Sorting imposes a global structure on the data so that extreme values become directly accessible.
2. Once sorted, we identify the two smallest elements at indices 0 and 1. These will form the pair that produces the smallest possible product. This is valid because in a sorted array, any other pair involving larger elements would only increase the product.
3. Next, we identify the two largest elements at indices n-2 and n-1. These form the pair that produces the largest possible product for the same reasoning in reverse: no other pair can exceed the product of the two largest elements.
4. We compute the product of the largest pair and subtract the product of the smallest pair. This gives us the maximum possible product difference.
5. Finally, we return this computed value as the result.

Why it works

The correctness relies on the ordering property of positive integers. Since all numbers are positive, the product of two numbers is monotonically increasing with respect to each operand. Therefore, the maximum product must come from the two largest numbers, and the minimum product must come from the two smallest numbers. Any deviation from these choices strictly reduces the resulting difference.

Python Solution

from typing import List

class Solution:
    def maxProductDifference(self, nums: List[int]) -> int:
        # Step 1: Sort the array
        nums.sort()
        
        # Step 2: Identify the two largest and two smallest numbers
        max1, max2 = nums[-1], nums[-2]
        min1, min2 = nums[0], nums[1]
        
        # Step 3: Compute and return the maximum product difference
        return (max1 * max2) - (min1 * min2)

The Python implementation follows the algorithm exactly. Sorting places the smallest elements at the start and the largest at the end. Extracting nums[0], nums[1], nums[-2], nums[-1] ensures we get the correct elements for the maximum product difference. nums.sort()

    n = len(nums)
    
    max_product = nums[n - 1] * nums[n - 2]
    min_product = nums[0] * nums[1]
    
    return max_product - min_product

### Explanation

The solution begins by sorting the input array, which ensures that the smallest values are at the front and the largest values are at the end. We then directly compute the product of the last two elements for the maximum pair product and the first two elements for the minimum pair product. Finally, we return their difference. Each step corresponds directly to the optimal strategy derived in the algorithm walkthrough.

## Go Solution

```go
import "sort"

func maxProductDifference(nums []int) int {
    // Step 1: Sort the slice
    sort.Ints(nums)
    
    // Step 2: Identify the two largest and two smallest numbers
    max1, max2 := nums[len(nums)-1], nums[len(nums)-2]
    min1, min2 := nums[0], nums[1]
    
    // Step 3: Compute and return the maximum product difference
    return (max1 * max2) - (min1 * min2)
}

The Go solution mirrors Python, with sort.Ints used for sorting. Go uses slices, so we access the elements with len(nums)-1 and len(nums)-2 to get the largest elements. All calculations are done with integers, so no extra handling is needed.

Worked Examples

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

1. Sort: [2, 4, 5, 6, 7]
2. Two largest: 6, 7
3. Two smallest: 2, 4
4. Maximum product difference: (6*7) - (2*4) = 42 - 8 = 34

Example 2: nums = [4,2,5,9,7,4,8]

1. Sort: [2, 4, 4, 5, 7, 8, 9]

2. Two largest: 8, 9

3. Two smallest: 2, 4

4. Maximum product difference: (8*9) - (2*4) = 72 - 8 = 64 sort.Ints(nums)

   n := len(nums)

   maxProduct := nums[n-1] * nums[n-2] minProduct := nums[0] * nums[1]

   return maxProduct - minProduct }

### Go-specific notes

In Go, we use `sort.Ints` to sort the slice in ascending order. Slices in Go are reference types, so sorting modifies the original array in place. Integer overflow is not a concern for this problem because constraints keep values small (`<= 10^4`), so products stay within 32-bit signed integer range.

## Worked Examples

### Example 1: nums = [5,6,2,7,4]

After sorting: `[2, 4, 5, 6, 7]`

| Step | Values |
| --- | --- |
| Smallest pair | 2, 4 |
| Largest pair | 6, 7 |
| Min product | 2 × 4 = 8 |
| Max product | 6 × 7 = 42 |
| Result | 42 - 8 = 34 |

### Example 2: nums = [4,2,5,9,7,4,8]

After sorting: `[2, 4, 4, 5, 7, 8, 9]`

| Step | Values |
| --- | --- |
| Smallest pair | 2, 4 |
| Largest pair | 8, 9 |
| Min product | 2 × 4 = 8 |
| Max product | 8 × 9 = 72 |
| Result | 72 - 8 = 64 |

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n log n) | Sorting dominates the runtime; extracting elements is O(1) |
| Space | O(1) | Sorting can be in-place; no additional data structures needed |

Sorting the array is the most expensive operation. Once sorted, accessing the required elements is constant time.
| Time | O(n log n) | Dominated by sorting the array |
| Space | O(1) or O(n) | Depends on sorting implementation |

The sorting step dominates the runtime, while the rest of the computation is constant time. No additional data structures are required beyond the input array.

## Test Cases

Provided examples

assert Solution().maxProductDifference([5,6,2,7,4]) == 34 # Example 1 assert Solution().maxProductDifference([4,2,5,9,7,4,8]) == 64 # Example 2

Edge case: minimal array length

assert Solution().maxProductDifference([1,2,3,4]) == (43)-(12) # 12-2=10

All elements the same

assert Solution().maxProductDifference([5,5,5,5,5]) == 0 # (55)-(55)=0

Large numbers

assert Solution().maxProductDifference([10000, 1, 10000, 1, 5000]) == (1000010000)-(11) # 100000000-1=99999999

Random unsorted

assert Solution().maxProductDifference([7,3,1,9,5,6]) == (97)-(13) # 63-3=60 assert Solution().maxProductDifference([5,6,2,7,4]) == 34 # basic example assert Solution().maxProductDifference([4,2,5,9,7,4,8]) == 64 # larger mixed case assert Solution().maxProductDifference([1,1,1,1]) == 0 # all equal elements assert Solution().maxProductDifference([1,2,3,4]) == 10 # smallest valid size assert Solution().maxProductDifference([10,10,1,1]) == 99 # clear extreme separation assert Solution().maxProductDifference([100,2,3,4]) == 392 # large outlier max

| Test | Why |
| --- | --- |
| `[5,6,2,7,4]` | Basic example with distinct numbers |
| `[4,2,5,9,7,4,8]` | Larger array with repeated numbers |
| `[1,2,3,4]` | Minimal length array, ensures function works with smallest allowed input |
| `[5,5,5,5,5]` | All elements equal, tests handling of zero difference |
| `[10000, 1, 10000, 1, 5000]` | Large values, tests integer handling |
| `[7,3,1,9,5,6]` | Random unsorted array, general correctness |

## Edge Cases

**1. Minimal length array (`nums.length = 4`)**

With exactly four elements, there is only one valid combination of indices. The solution still works because sorting and selecting the first two and last two elements covers all four numbers, producing the correct result.

**2. All numbers are equal**

When all elements are the same, the maximum product difference is zero. The algorithm handles this naturally because `(max1*max2)-(min1*min2)` results in zero if `max1 = max2 = min1 = min2`.

**3. Large numbers near upper bound**

Arrays with elements near `10^4` could potentially cause overflow in languages with fixed integer sizes, but in Python, integers are unbounded. In Go, the problem constraints guarantee that the product `(10000*10000)` fits within a 32-bit integer, but for very large arrays, using `int64` would be safer in production. The algorithm still functions correctly under these constraints.
| [5,6,2,7,4] | validates standard example behavior |
| [1,1,1,1] | checks uniform array handling |
| [1,2,3,4] | checks minimal valid input size |
| [10,10,1,1] | tests symmetric duplicates at extremes |
| [100,2,3,4] | tests dominance of extreme values |

## Edge Cases

One important edge case is when all elements are identical. In this situation, both the maximum and minimum pair products are equal, so the result is zero. The sorting-based approach handles this naturally since both extremes pick identical values.

Another edge case occurs when the array size is exactly four. In this case, there is only one valid partition into two pairs, so the solution still works correctly because the sorted extremes correspond exactly to the only possible grouping.

A third edge case involves repeated large or small values. Even when duplicates exist, selecting the two largest and two smallest indices still produces the optimal result because any alternative pairing would either reduce the maximum product or increase the minimum product, worsening the difference.