Remove One Element to Make the Array Strictly Increasing - Solution & Explanation
Problem Statement
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] <= 1000
Approach Overview
Problem 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 1: Direct Iteration and Check
This approach involves iterating through the array to find any violation of the strictly increasing condition. If a violation is found, we check if removing either of the elements involved in this violation (the current one or the previous one) resolves the issue. We maintain a count of such violations and decide the result based on this count.
We iterate through the array to check where the strict increasing condition fails. If a violation is found, we increment a count. If this count exceeds one, we return false. We further verify if removing either of the problematic elements allows the array to be strictly increasing. This is done by comparing the element prior to the last strict pair and the element after the current one.
Complexity
Time complexity is O(n) due to single-pass iteration. Space complexity is O(1) as no extra storage is used besides counters.
Approach 2: Simulated Removal
By simulating the removal of each element one by one, we can explicitly check if the array becomes strictly increasing with that removal. This involves a straightforward check but iterated for each index.
Simulating the removal for each index: the `isStrictlyIncreasing` function skips the specified index and checks the rest for strict increase. If any scenario where a single removal works, the main function returns true.
Complexity
Time complexity: O(n^2), as each element removal simulation involves another pass. Space complexity: O(1), as no additional data structures are used.
Approach 3: Traversal
We can traverse the array to find the first position i where nums[i] < nums[i+1] is not satisfied. Then, we check if the array is strictly increasing after removing either i or i+1. If it is, we return true; otherwise, we return false.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Direct Iteration and Check | Time complexity is O(n) due to single-pass iteration. Space complexity is O(1) as no extra storage is used besides counters. |
| Simulated Removal | Time complexity: O(n^2), as each element removal simulation involves another pass. Space complexity: O(1), as no additional data structures are used. |
| Traversal | — |
Detailed Complexity Analysis
| 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 |
Video Solution
1909. Remove One Element to Make the Array Strictly Increasing - Leetcode Biweekly Contest 55 • Haridas Dutt • 7,172 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Remove One Element to Make the Array Strictly Increasing easy or hard?
Remove One Element to Make the Array Strictly Increasing Python/Java solution
How to solve Remove One Element to Make the Array Strictly Increasing in O(n)?
What is the best approach for Remove One Element to Make the Array Strictly Increasing?
Is Remove One Element to Make the Array Strictly Increasing asked at Google/Amazon/Meta?
What data structure is used in Remove One Element to Make the Array Strictly Increasing?
What is the time complexity of Remove One Element to Make the Array Strictly Increasing?
Ready to solve this problem?
Practice Remove One Element to Make the Array Strictly Increasing with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor