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.
Constraints:
2 <= nums.length <= 10001 <= nums[i] <= 1000In #1909 Remove One Element to Make the Array Strictly Increasing, the goal is to determine whether removing at most one element can make the array strictly increasing. A strictly increasing array requires every element to be greater than its previous one.
An efficient approach is to perform a single pass through the array and count the number of violations where nums[i] <= nums[i-1]. If more than one such violation appears, it is impossible to fix the sequence with only one removal.
When a violation occurs, carefully decide whether removing the current element or the previous one would maintain the increasing property. This can be checked by comparing surrounding values such as nums[i], nums[i-1], and nums[i-2]. By validating the local ordering, you can simulate the removal logically without actually modifying the array.
This greedy validation works because only one problematic position can exist. The algorithm runs in O(n) time with O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Single Pass Greedy Check | O(n) | O(1) |
Haridas Dutt
Use these hints if you're stuck. Try solving on your own first.
For each index i in nums remove this index.
If the array becomes sorted return true, otherwise revert to the original array and try different index.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Checking neighboring elements helps determine whether removing the current element or the previous one keeps the sequence strictly increasing. This local check ensures the array can still maintain the correct order after one simulated removal.
While this exact problem may not always appear, similar array validation and greedy problems are common in FAANG-style interviews. Interviewers often test the ability to detect local violations and handle edge cases efficiently.
The problem mainly uses an array traversal and does not require complex data structures. A few variables to track violations and compare neighboring elements are sufficient, allowing an efficient O(1) extra space solution.
The optimal approach is a single-pass greedy check that counts violations where the increasing order breaks. If more than one violation occurs, the array cannot be fixed with a single removal. Otherwise, validate whether removing the current or previous element restores the increasing order.