{"id":9227,"date":"2021-12-24T19:02:32","date_gmt":"2021-12-25T03:02:32","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9227"},"modified":"2021-12-24T19:03:57","modified_gmt":"2021-12-25T03:03:57","slug":"leetcode-1913-maximum-product-difference-between-two-pairs","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-1913-maximum-product-difference-between-two-pairs\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1913. Maximum Product Difference Between Two Pairs"},"content":{"rendered":"\n<p>The&nbsp;<strong>product difference<\/strong>&nbsp;between two pairs&nbsp;<code>(a, b)<\/code>&nbsp;and&nbsp;<code>(c, d)<\/code>&nbsp;is defined as&nbsp;<code>(a * b) - (c * d)<\/code>.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>For example, the product difference between&nbsp;<code>(5, 6)<\/code>&nbsp;and&nbsp;<code>(2, 7)<\/code>&nbsp;is&nbsp;<code>(5 * 6) - (2 * 7) = 16<\/code>.<\/li><\/ul>\n\n\n\n<p>Given an integer array&nbsp;<code>nums<\/code>, choose four&nbsp;<strong>distinct<\/strong>&nbsp;indices&nbsp;<code>w<\/code>,&nbsp;<code>x<\/code>,&nbsp;<code>y<\/code>, and&nbsp;<code>z<\/code>&nbsp;such that the&nbsp;<strong>product difference<\/strong>&nbsp;between pairs&nbsp;<code>(nums[w], nums[x])<\/code>&nbsp;and&nbsp;<code>(nums[y], nums[z])<\/code>&nbsp;is&nbsp;<strong>maximized<\/strong>.<\/p>\n\n\n\n<p>Return&nbsp;<em>the&nbsp;<strong>maximum<\/strong>&nbsp;such product difference<\/em>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [5,6,2,7,4]\n<strong>Output:<\/strong> 34\n<strong>Explanation:<\/strong> We can choose indices 1 and 3 for the first pair (6, 7) and indices 2 and 4 for the second pair (2, 4).\nThe product difference is (6 * 7) - (2 * 4) = 34.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [4,2,5,9,7,4,8]\n<strong>Output:<\/strong> 64\n<strong>Explanation:<\/strong> We can choose indices 3 and 6 for the first pair (9, 8) and indices 1 and 5 for the second pair (2, 4).\nThe product difference is (9 * 8) - (2 * 4) = 64.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>4 &lt;= nums.length &lt;= 10<sup>4<\/sup><\/code><\/li><li><code>1 &lt;= nums[i] &lt;= 10<sup>4<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Greedy<\/strong><\/h2>\n\n\n\n<p>Since all the numbers are positive, we just need to find the largest two numbers as the first pair and smallest two numbers are the second pair.<\/p>\n\n\n\n<p>Time complexity: O(nlogn) \/ sorting, O(n) \/ finding min\/max elements.<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int maxProductDifference(vector<int>& nums) {\n    const int n = nums.size();\n    sort(begin(nums), end(nums));\n    return nums[n - 1] * nums[n - 2] - nums[0] * nums[1];\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua\nclass Solution:\n  def maxProductDifference(self, nums: List[int]) -> int:\n    nums.sort()\n    return nums[-1] * nums[-2] - nums[0] * nums[1]\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>The&nbsp;product difference&nbsp;between two pairs&nbsp;(a, b)&nbsp;and&nbsp;(c, d)&nbsp;is defined as&nbsp;(a * b) &#8211; (c * d). For example, the product difference between&nbsp;(5, 6)&nbsp;and&nbsp;(2, 7)&nbsp;is&nbsp;(5 * 6) -&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51],"tags":[222,88,148,15],"class_list":["post-9227","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-easy","tag-greedy","tag-pair","tag-sorting","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9227","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9227"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9227\/revisions"}],"predecessor-version":[{"id":9229,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9227\/revisions\/9229"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9227"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9227"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9227"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}