Remove One Element to Make the Array Strictly Increasing
Problem
Decide whether removing at most one element from nums leaves it strictly increasing.
nums = [1,2,10,5,7]truedef can_be_increasing(nums):
def strict(a):
return all(a[i] < a[i+1] for i in range(len(a) - 1))
bad = -1
for i in range(len(nums) - 1):
if nums[i] >= nums[i+1]:
if bad != -1: return False
bad = i
if bad == -1: return True
return strict(nums[:bad] + nums[bad+1:]) or strict(nums[:bad+1] + nums[bad+2:])function canBeIncreasing(nums) {
function strict(a) { for (let i = 0; i < a.length - 1; i++) if (a[i] >= a[i+1]) return false; return true; }
let bad = -1;
for (let i = 0; i < nums.length - 1; i++) {
if (nums[i] >= nums[i+1]) { if (bad !== -1) return false; bad = i; }
}
if (bad === -1) return true;
return strict([...nums.slice(0, bad), ...nums.slice(bad+1)]) || strict([...nums.slice(0, bad+1), ...nums.slice(bad+2)]);
}class Solution {
boolean strict(int[] a, int skip) {
Integer prev = null;
for (int i = 0; i < a.length; i++) {
if (i == skip) continue;
if (prev != null && a[i] <= prev) return false;
prev = a[i];
}
return true;
}
public boolean canBeIncreasing(int[] nums) {
int bad = -1;
for (int i = 0; i < nums.length - 1; i++) if (nums[i] >= nums[i+1]) { if (bad != -1) return false; bad = i; }
if (bad == -1) return true;
return strict(nums, bad) || strict(nums, bad + 1);
}
}bool strictSkip(vector<int>& a, int skip) {
int prev = INT_MIN; bool first = true;
for (int i = 0; i < (int)a.size(); i++) {
if (i == skip) continue;
if (!first && a[i] <= prev) return false;
prev = a[i]; first = false;
}
return true;
}
bool canBeIncreasing(vector<int>& nums) {
int bad = -1;
for (int i = 0; i + 1 < (int)nums.size(); i++) if (nums[i] >= nums[i+1]) { if (bad != -1) return false; bad = i; }
if (bad == -1) return true;
return strictSkip(nums, bad) || strictSkip(nums, bad + 1);
}Explanation
We are allowed to delete at most one element to make the array strictly increasing. The key insight is that we only need to look at the first place where the order breaks — everything before it is already fine.
First we scan for a violation: an index i where nums[i] >= nums[i+1]. If we find a second violation, no single deletion can fix two separate problems, so we return false immediately. If we find none, the array is already strict and the answer is true.
When there is exactly one violation at index bad, the offending pair is nums[bad] and nums[bad+1]. We try two repairs: remove the left one, or remove the right one. The helper strict checks whether the array is strictly increasing when one index is skipped. If either removal yields a strict sequence, we return true.
Example: nums = [1, 2, 10, 5, 7]. The first break is 10 >= 5 at bad = 2. Removing index 2 (10) gives [1, 2, 5, 7], which is strict, so the answer is true.
We only ever rescan the array a constant number of times, so this stays linear time and uses essentially no extra space.