Watch 10 video solutions for Remove One Element to Make the Array Strictly Increasing, a easy level problem involving Array. This walkthrough by Haridas Dutt has 7,120 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text 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.
Constraints:
2 <= nums.length <= 10001 <= nums[i] <= 1000Problem Overview: Given an integer array, determine whether removing exactly one element (or possibly none) can make the sequence strictly increasing. The final array must satisfy nums[i] < nums[i+1] for every adjacent pair.
Approach 1: Simulated Removal (O(n^2) time, O(1) space)
The straightforward method tries removing each index and checks whether the remaining array is strictly increasing. For every position i, skip that element and iterate through the rest while verifying nums[j] < nums[j+1]. If any simulated removal produces a valid sequence, return true. This approach is easy to reason about and useful for verifying correctness, but it scans the array repeatedly, which leads to quadratic time complexity.
Approach 2: Direct Iteration and Check (O(n) time, O(1) space)
A single pass greedy check is enough. Iterate through the array and count violations where nums[i] <= nums[i-1]. A strictly increasing array can have at most one such violation if removing one element fixes it. When a violation appears, decide which element to logically remove: either the previous element or the current one. Compare nums[i] with nums[i-2] to determine if removing the previous element keeps the sequence valid; otherwise treat the current element as removed. If more than one violation occurs, forming a strictly increasing sequence with one removal is impossible.
This greedy observation works because only local comparisons determine whether the increasing property breaks. Once you encounter more than one invalid pair, no single deletion can repair the entire sequence.
Recommended for interviews: The direct iteration approach is the expected solution. It runs in O(n) time with O(1) extra space and shows you understand greedy reasoning on arrays. Simulated removal is acceptable as a first thought, but interviewers usually expect the linear scan optimization.
Problems like this commonly appear in array and greedy pattern discussions, where a single pass detects structural violations. Similar logic also appears in some two pointers style validation problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulated Removal | O(n^2) | O(1) | Good for initial reasoning or brute-force validation of the rule |
| Direct Iteration and Check (Greedy) | O(n) | O(1) | Optimal approach for interviews and production code |