Formatted question description: https://leetcode.ca/all/1909.html
1909. Remove One Element to Make the Array Strictly Increasing
Level
Easy
Description
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
Solution
For each index, try to remove the element at the index and check whether the remaining elements are strictly increasing. If there exists at least one element that makes the remaining elements strictly increasing, return true
. Otherwise, return false
.
If the array is already strictly increasing, then after removing any element, the remaining elements are also strictly increasing, so return true
.
class Solution {
public boolean canBeIncreasing(int[] nums) {
int length = nums.length;
for (int i = 0; i < length; i++) {
if (isIncreasing(nums, i))
return true;
}
return false;
}
public boolean isIncreasing(int[] nums, int index) {
int length = nums.length;
int prev = -1;
for (int i = 0; i < length; i++) {
if (i != index) {
int curr = nums[i];
if (curr <= prev)
return false;
prev = curr;
}
}
return true;
}
}