Remove One Element to Make the Array Strictly Increasing Solution
Remove One Element to Make the Array Strictly Increasing solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Remove One Element to Make the Array Strictly Increasing is an easy coding problem on arrays and greedy, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays, Greedy
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Return true if deleting exactly one element of nums leaves an array that is strictly increasing — every element smaller than the one after it. Otherwise return false.
If nums is already strictly increasing the answer is true, since deleting any element keeps it that way.
Example 1
Input: nums = [3,8,5,9]
Output: true
Explanation: Deleting 8 leaves [3,5,9].
Example 2
Input: nums = [4,6,2,5]
Output: false
Explanation: Every single deletion still leaves a descent.
Example 3
Input: nums = [7,7]
Output: true
Explanation: Deleting either 7 leaves [7].
Constraints
2 <= nums.length <= 10001 <= nums[i] <= 1000
Hints for Remove One Element to Make the Array Strictly Increasing
Hint 1
Walk left to right and look for the first place where
nums[i - 1] >= nums[i].Hint 2
At such a conflict you must delete one of the two. Two conflicts that need two deletions mean
false.Hint 3
Prefer deleting
nums[i - 1](it keeps the last kept value small) — but only ifnums[i - 2] < nums[i]; otherwise deletenums[i].
How to solve Remove One Element to Make the Array Strictly Increasing
Scan once, remembering the last value kept. The first conflict forces a deletion, and the better choice is the one that leaves the smaller last value, as long as it keeps the prefix increasing.
Approach
- Set
prev = nums[0]andremoved = false. - For each
i >= 1: ifnums[i] > prev, setprev = nums[i]and continue. - Otherwise, if
removedis already true, returnfalse; setremoved = true. - If
i == 1ornums[i - 2] < nums[i], deletenums[i - 1]by settingprev = nums[i]; else deletenums[i]by leavingprevunchanged. - Return
trueafter the scan.
Why it works
Before the first conflict nothing has been deleted, so the kept prefix is nums[0..i-1] and the element before nums[i - 1] is nums[i - 2]. Deleting nums[i - 1] is allowed only if nums[i - 2] < nums[i], and when it is allowed it leaves the last kept value nums[i] <= nums[i - 1], which can only make the rest easier. Any later conflict needs a second deletion, so it means false.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Strictly increasing: equal neighbours are a conflict.
- Deleting
nums[i - 1]without checkingnums[i - 2] < nums[i]wrongly accepts[5,6,1,2]; always deletingnums[i]instead wrongly rejects[1,9,3,4], where 9 is the one to drop. - Do not modify the input array in languages where it is shared with the caller — track
previnstead.
Reference solution
Python
from typing import List
def canBeIncreasing(nums: List[int]) -> bool:
prev = nums[0]
removed = False
for i in range(1, len(nums)):
if nums[i] > prev:
prev = nums[i]
continue
if removed:
return False
removed = True
if i == 1 or nums[i - 2] < nums[i]:
prev = nums[i]
return TrueJava
public static boolean canBeIncreasing(int[] nums) {
int prev = nums[0];
boolean removed = false;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > prev) {
prev = nums[i];
continue;
}
if (removed) return false;
removed = true;
if (i == 1 || nums[i - 2] < nums[i]) prev = nums[i];
}
return true;
}C++
bool canBeIncreasing(vector<int>& nums) {
int prev = nums[0];
bool removed = false;
for (int i = 1; i < (int)nums.size(); i++) {
if (nums[i] > prev) {
prev = nums[i];
continue;
}
if (removed) return false;
removed = true;
if (i == 1 || nums[i - 2] < nums[i]) prev = nums[i];
}
return true;
}JavaScript
var canBeIncreasing = function(nums) {
var prev = nums[0], removed = false;
for (var i = 1; i < nums.length; i++) {
if (nums[i] > prev) {
prev = nums[i];
continue;
}
if (removed) return false;
removed = true;
if (i === 1 || nums[i - 2] < nums[i]) prev = nums[i];
}
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms