We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Product Difference Between Two Pairs

Number: 2042

Difficulty: Easy

Paid? No

Companies: Google, Apple, Amazon

Problem Description

Given an integer array nums, choose four distinct indices such that the product difference between the pairs (nums[w], nums[x]) and (nums[y], nums[z]) is maximized. The product difference is defined as (a * b) - (c * d), where (a, b) is one pair and (c, d) is the other pair.

Key Insights

  • The maximum product difference is achieved by maximizing one product and minimizing the other product.
  • Sorting the array allows us to directly pick the two largest and the two smallest numbers.
  • After sorting, the two largest numbers are at the end and the two smallest numbers are at the beginning of the array.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting. Space Complexity: O(log n) to O(n) depending on the sorting algorithm’s space requirements (often O(log n) with in-place sorting).

Solution

The solution uses sorting to rearrange the array. Once sorted, the two largest elements (located at the end of the array) yield the maximum product, while the two smallest (at the beginning) yield the minimum product. The answer is then computed as the difference between these two products.

Code Solutions

# Python implementation with clear variable names and comments
def maxProductDifference(nums):
    # Sort the array to easily obtain the smallest and largest values
    nums.sort()
    # The two largest numbers are at the end and the two smallest numbers are at the beginning
    max_product = nums[-1] * nums[-2]
    min_product = nums[0] * nums[1]
    # Calculate and return the maximum product difference
    return max_product - min_product

# Example usage:
# print(maxProductDifference([5, 6, 2, 7, 4]))
← Back to All Questions