{"id":9866,"date":"2022-10-15T21:56:53","date_gmt":"2022-10-16T04:56:53","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9866"},"modified":"2022-10-16T13:50:07","modified_gmt":"2022-10-16T20:50:07","slug":"leetcode-2441-largest-positive-integer-that-exists-with-its-negative%ef%bf%bc%ef%bf%bc","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-2441-largest-positive-integer-that-exists-with-its-negative%ef%bf%bc%ef%bf%bc\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2441.\u00a0Largest Positive Integer That Exists With Its Negative"},"content":{"rendered":"\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 2441. Largest Positive Integer That Exists With Its Negative - \u5237\u9898\u627e\u5de5\u4f5c EP404\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/HItywpd0-yY?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>Given an integer array&nbsp;<code>nums<\/code>&nbsp;that&nbsp;<strong>does not contain<\/strong>&nbsp;any zeros, find&nbsp;<strong>the largest positive<\/strong>&nbsp;integer&nbsp;<code>k<\/code>&nbsp;such that&nbsp;<code>-k<\/code>&nbsp;also exists in the array.<\/p>\n\n\n\n<p>Return&nbsp;<em>the positive integer&nbsp;<\/em><code>k<\/code>. If there is no such integer, return&nbsp;<code>-1<\/code>.<\/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 = [-1,2,-3,3]\n<strong>Output:<\/strong> 3\n<strong>Explanation:<\/strong> 3 is the only valid k we can find in the array.\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 = [-1,10,6,7,-7,1]\n<strong>Output:<\/strong> 7\n<strong>Explanation:<\/strong> Both 1 and 7 have their corresponding negative values in the array. 7 has a larger value.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [-10,8,6,7,-2,-3]\n<strong>Output:<\/strong> -1\n<strong>Explanation:<\/strong> There is no a single valid k, we return -1.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= nums.length &lt;= 1000<\/code><\/li><li><code>-1000 &lt;= nums[i] &lt;= 1000<\/code><\/li><li><code>nums[i] != 0<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Hashtable<\/strong><\/h2>\n\n\n\n<p>We can do in one pass by checking whether -x in the hashtable and update ans with abs(x) if so.<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(n)<\/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 findMaxK(vector<int>& nums) {\n    unordered_set<int> s;\n    int ans = -1;\n    for (int x : nums) {\n      if (abs(x) > ans && s.count(-x))\n        ans = abs(x);\n      s.insert(x);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Sorting<\/strong><\/h2>\n\n\n\n<p>Sort the array by abs(x) in descending order.<\/p>\n\n\n\n<p>[-1,10,6,7,-7,1] becomes = [-1, 1, 6, -7, 7, 10]<\/p>\n\n\n\n<p>Check whether arr[i] = -arr[i-1].<\/p>\n\n\n\n<p>Time complexity: O(nlogn)<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 findMaxK(vector<int>& nums) {\n    sort(begin(nums), end(nums), [](int a, int b){\n      return abs(a) == abs(b) ? a < b : abs(a) > abs(b);\n    });    \n    for (int i = 1; i < nums.size(); ++i)\n      if (nums[i] == -nums[i - 1]) return nums[i];\n    return -1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 3: Two Pointers<\/strong><\/h2>\n\n\n\n<p>Sort the array.<\/p>\n\n\n\n<p>Let sum = nums[i] + nums[j], sum == 0, we find one pair, if sum &lt; 0, ++i else --j.<\/p>\n\n\n\n<p>Time complexity: O(nlogn)<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 findMaxK(vector<int>& nums) {\n    sort(begin(nums), end(nums));\n    int ans = -1;\n    for (int i = 0, j = nums.size() - 1; i < j; ) {\n      const int s = nums[i] + nums[j];\n      if (s == 0) {\n        ans = max(ans, nums[j]);\n        ++i, --j;      \n      } else if (s < 0) {\n        ++i;\n      } else {\n        --j;\n      }      \n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given an integer array&nbsp;nums&nbsp;that&nbsp;does not contain&nbsp;any zeros, find&nbsp;the largest positive&nbsp;integer&nbsp;k&nbsp;such that&nbsp;-k&nbsp;also exists in the array. Return&nbsp;the positive integer&nbsp;k. If there is no such integer, return&nbsp;-1.&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[704,20,222,82,23],"class_list":["post-9866","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-abs","tag-array","tag-easy","tag-hashtable","tag-sort","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9866","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=9866"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9866\/revisions"}],"predecessor-version":[{"id":9872,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9866\/revisions\/9872"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9866"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9866"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9866"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}