{"id":9219,"date":"2021-12-24T00:31:24","date_gmt":"2021-12-24T08:31:24","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9219"},"modified":"2021-12-24T00:38:42","modified_gmt":"2021-12-24T08:38:42","slug":"leetcode-1909-remove-one-element-to-make-the-array-strictly-increasing","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-1909-remove-one-element-to-make-the-array-strictly-increasing\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1909. Remove One Element to Make the Array Strictly Increasing"},"content":{"rendered":"\n

Given a 0-indexed<\/strong> integer array nums<\/code>, return true<\/code> if it can be made strictly increasing<\/strong> after removing exactly one<\/strong> element, or <\/em>false<\/code> otherwise. If the array is already strictly increasing, return <\/em>true<\/code>.<\/p>\n\n\n\n

The array nums<\/code> is strictly increasing<\/strong> if nums[i - 1] < nums[i]<\/code> for each index (1 <= i < nums.length).<\/code><\/p>\n\n\n\n

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

Input:<\/strong> nums = [1,2,10,5,7]\nOutput:<\/strong> true\nExplanation:<\/strong> By removing 10 at index 2 from nums, it becomes [1,2,5,7].\n[1,2,5,7] is strictly increasing, so return true.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [2,3,1,2]\nOutput:<\/strong> false\nExplanation:<\/strong>\n[3,1,2] is the result of removing the element at index 0.\n[2,1,2] is the result of removing the element at index 1.\n[2,3,2] is the result of removing the element at index 2.\n[2,3,1] is the result of removing the element at index 3.\nNo resulting array is strictly increasing, so return false.<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [1,1,1]\nOutput:<\/strong> false\nExplanation:<\/strong> The result of removing any element is [1,1].\n[1,1] is not strictly increasing, so return false.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 2 <= nums.length <= 1000<\/code><\/li>
  • 1 <= nums[i] <= 1000<\/code><\/li><\/ul>\n\n\n\n
    Solution 1: Brute Force<\/strong><\/h2>\n\n\n\n
    Enumerate the element to remove and check.<\/p>\n\n\n\n
    Time complexity: O(n2<\/sup>)
    Space complexity: O(n) -> O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  bool canBeIncreasing(vector& nums) {\n    const int n = nums.size();\n    auto check = [&](int k) {\n      vector arr(nums);\n      arr.erase(begin(arr) + k);\n      for (int i = 1; i < n - 1; ++i)\n        if (arr[i] <= arr[i - 1]) return false;\n      return true;\n    };\n    for (int i = 0; i < n; ++i)\n      if (check(i)) return true;\n    return false;\n  }\n};\n<\/pre>\n\n<\/div>
    C++\/O(1) Space<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  bool canBeIncreasing(vector& nums) {\n    const int n = nums.size();\n    auto check = [&](int k) {      \n      for (int i = 1; i < n; ++i) {        \n        int j = (i - 1 == k) ? (i - 2) : (i - 1);\n        if (i != k && j >= 0 && nums[i] <= nums[j])          \n          return false;\n      }\n      return true;\n    };\n    for (int i = 0; i < n; ++i)\n      if (check(i)) return true;\n    return false;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Given a 0-indexed integer array nums, return true if it can be made strictly increasing after removing exactly one element, or false otherwise. If the array is already strictly increasing, return true. The array nums is strictly increasing if nums[i – 1]…<\/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,749],"class_list":["post-9219","post","type-post","status-publish","format-standard","hentry","category-array","tag-array","tag-gready","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9219","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=9219"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9219\/revisions"}],"predecessor-version":[{"id":9222,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9219\/revisions\/9222"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9219"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9219"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9219"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}