2023-12-18 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's December LeetCoding Challenge with cpp.

December LeetCoding Challenge 18

Description

Maximum Product Difference Between Two Pairs

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 <= 104
  • 1 <= nums[i] <= 104

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();

class Solution {
public:
  int maxProductDifference(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    return nums.back() * nums[nums.size() - 2] - nums[0] * nums[1];
  }
};

// Accepted
// 96/96 cases passed (14 ms)
// Your runtime beats 96.75 % of cpp submissions
// Your memory usage beats 9.65 % of cpp submissions (20.8 MB)
Algorithm