{"id":8856,"date":"2021-11-28T09:02:02","date_gmt":"2021-11-28T17:02:02","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8856"},"modified":"2021-11-28T09:02:31","modified_gmt":"2021-11-28T17:02:31","slug":"leetcode-2091-removing-minimum-and-maximum-from-array","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-2091-removing-minimum-and-maximum-from-array\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2091. Removing Minimum and Maximum From Array"},"content":{"rendered":"\n

You are given a 0-indexed<\/strong> array of distinct<\/strong> integers nums<\/code>.<\/p>\n\n\n\n

There is an element in nums<\/code> that has the lowest<\/strong> value and an element that has the highest<\/strong> value. We call them the minimum<\/strong> and maximum<\/strong> respectively. Your goal is to remove both<\/strong> these elements from the array.<\/p>\n\n\n\n

A deletion<\/strong> is defined as either removing an element from the front<\/strong> of the array or removing an element from the back<\/strong> of the array.<\/p>\n\n\n\n

Return the minimum<\/strong> number of deletions it would take to remove both<\/strong> the minimum and maximum element from the array.<\/em><\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> nums = [2,10<\/strong>,7,5,4,1<\/strong>,8,6]\nOutput:<\/strong> 5\nExplanation:<\/strong> \nThe minimum element in the array is nums[5], which is 1.\nThe maximum element in the array is nums[1], which is 10.\nWe can remove both the minimum and maximum by removing 2 elements from the front and 3 elements from the back.\nThis results in 2 + 3 = 5 deletions, which is the minimum number possible.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [0,-4<\/strong>,19<\/strong>,1,8,-2,-3,5]\nOutput:<\/strong> 3\nExplanation:<\/strong> \nThe minimum element in the array is nums[1], which is -4.\nThe maximum element in the array is nums[2], which is 19.\nWe can remove both the minimum and maximum by removing 3 elements from the front.\nThis results in only 3 deletions, which is the minimum number possible.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [101<\/strong>]\nOutput:<\/strong> 1\nExplanation:<\/strong>  \nThere is only one element in the array, which makes it both the minimum and maximum element.\nWe can remove it with 1 deletion.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= nums.length <= 105<\/sup><\/code><\/li>
  • -105<\/sup> <= nums[i] <= 105<\/sup><\/code><\/li>
  • The integers in nums<\/code> are distinct<\/strong>.<\/li><\/ul>\n\n\n\n
    Solution: Three ways<\/strong><\/h2>\n\n\n\n
    There are only three ways to remove min\/max elements.
    1) Remove front elements
    2) Remove back elements
    3) Remove one with front elements, and another one with back elements.<\/p>\n\n\n\n
    Just find the best way to do it.<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int minimumDeletions(vector& nums) {\n    const int n = nums.size();\n    auto [it1, it2] = minmax_element(begin(nums), end(nums));\n    int i = it1 - begin(nums);\n    int j = it2 - begin(nums);\n    return min({max(i, j) + 1, \/\/ remove front elements\n                n - min(i, j), \/\/ remove back elements\n                min(i, j) + 1 + n - max(i, j)} \/\/ front + back\n              );    \n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given a 0-indexed array of distinct integers nums. There is an element in nums that has the lowest value and an element that has the highest value. We call them the minimum and maximum respectively. Your goal is…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[20,177],"class_list":["post-8856","post","type-post","status-publish","format-standard","hentry","category-array","tag-array","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8856","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=8856"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8856\/revisions"}],"predecessor-version":[{"id":8858,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8856\/revisions\/8858"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8856"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8856"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8856"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}