Contents
Remove One Element to Make the Array Strictly Increasing Solution
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
- While travesring through the array Ill keep checking the strictly increasing sequence for the condition
- and when the condition doesn’t satisfy the condition A[i] < A[i+1]:
- Then we know for sure that we have to remove either of these two
- here comes the main part i.e, which one to remove when you have a chance to remove both:
- then it’s always better to remove the first one.
- You’ll better understand it when you draw them as a graph on the paper
Program: Remove One Element to Make the Array Strictly Increasing in Java
class Solution {
public:
bool canBeIncreasing(vector<int>& nums) {
int n=nums.size();
int chances=1; // i have only one chance to remove a number
int i=0;
while(i<nums.size()-1){
if(nums[i]>=nums[i+1]){
if(chances==0)return false;
if(i==0){
nums[i]=nums[i+1]-1;
}
else{
if(nums[i+1]>nums[i-1])nums[i]=nums[i-1];
else nums[i+1]=nums[i];
}
chances--;
}
i++;
}
return true;
}
};