algoadvance

Leetcode 1913. Maximum Product Difference Between Two Pairs

Problem Statement

Given an integer array nums, choose four distinct indices w, x, y, and z such that the product difference between the two pairs (nums[w] * nums[x]) and (nums[y] * nums[z]) is maximized.

Return the maximum product difference.

Clarifying Questions

  1. Constraints on the input array?
    • The array nums has at least 4 elements.
    • All elements in nums are non-negative integers.
  2. Output specifics?
    • We need to return a single integer value which is the maximum product difference between two pairs.
  3. Allowed values for the elements in the array?
    • The values can range broadly within the limits of typical integer storage in C++.

Strategy

To achieve the maximum product difference, notice that:

Steps:

  1. Sort the array nums in ascending order.
  2. The two largest numbers will then be the last two elements of the sorted array.
  3. The two smallest numbers will be the first two elements of the sorted array.
  4. Compute the product of the two largest numbers.
  5. Compute the product of the two smallest numbers.
  6. The result is the difference between the product of the two largest numbers and the product of the two smallest numbers.

Code

#include <iostream>
#include <vector>
#include <algorithm>

int maxProductDifference(std::vector<int>& nums) {
    std::sort(nums.begin(), nums.end());
    int n = nums.size();
    int maxProduct = nums[n-1] * nums[n-2];
    int minProduct = nums[0] * nums[1];
    return maxProduct - minProduct;
}

int main() {
    std::vector<int> nums = {5, 6, 2, 7, 4};
    std::cout << "Maximum Product Difference: " << maxProductDifference(nums) << std::endl;
    return 0;
}

Time Complexity

Therefore, the overall time complexity is (O(n \log n)).

This strategy ensures that we efficiently compute the maximum product difference as required by identifying the largest and smallest numbers through sorting.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI