1909

1909. Remove One Element to Make the Array Strictly Increasing (Easy)

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] < nums[i] for each index (1 <= i < nums.length).

 

Example 1:

Input: nums = [1,2,10,5,7]
Output: true
Explanation: By removing 10 at index 2 from nums, it becomes [1,2,5,7].
[1,2,5,7] is strictly increasing, so return true.

Example 2:

Input: nums = [2,3,1,2]
Output: false
Explanation:
[3,1,2] is the result of removing the element at index 0.
[2,1,2] is the result of removing the element at index 1.
[2,3,2] is the result of removing the element at index 2.
[2,3,1] is the result of removing the element at index 3.
No resulting array is strictly increasing, so return false.

Example 3:

Input: nums = [1,1,1]
Output: false
Explanation: The result of removing any element is [1,1].
[1,1] is not strictly increasing, so return false.

Example 4:

Input: nums = [1,2,3]
Output: true
Explanation: [1,2,3] is already strictly increasing, so return true.

 

Constraints:

• 2 <= nums.length <= 1000
• 1 <= nums[i] <= 1000

Companies:
eBay

Related Topics:
Array

Solution 1. Brute Force

// OJ: https://leetcode.com/problems/remove-one-element-to-make-the-array-strictly-increasing/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    bool canBeIncreasing(vector<int>& A) {
        int N = A.size();
        for (int i = 0; i < N; ++i) {
            bool good = true;
            int prev = 0;
            for (int j = 0; j < N && good; ++j) {
                if (i == j) continue;
                good = A[j] > prev;
                prev = A[j];
            }
            if (good) return true;
        }
        return false;
    }
};

Solution 2.

When A[i] <= A[i - 1], we need to delete either A[i] or A[i - 1].

• If A[i] > A[i - 2], we should delete A[i - 1]. Then let prev = A[i].
• If A[i] <= A[i - 2], we should delete A[i]. Then keep prev = A[i - 1].

// OJ: https://leetcode.com/problems/remove-one-element-to-make-the-array-strictly-increasing/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    bool canBeIncreasing(vector<int>& A) {
        int N = A.size(), prev = A[0];
        bool used = false;
        for (int i = 1; i < N; ++i) {
            if (A[i] > prev) prev = A[i];
            else {
                if (used) return false;
                used = true;
                if (i - 2 < 0 || A[i - 2] < A[i]) prev = A[i];
            }
        }
        return true;
    }
};