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] <= 1000This 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.
C++
Java
Python
C#
JavaScript
Time complexity is O(n) due to single-pass iteration. Space complexity is O(1) as no extra storage is used besides counters.
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.
C++
Java
Python
C#
JavaScript
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 | 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. |
1909. Remove One Element to Make the Array Strictly Increasing - Leetcode Biweekly Contest 55 • Haridas Dutt • 6,991 views views
Watch 9 more video solutions →Practice Remove One Element to Make the Array Strictly Increasing with our built-in code editor and test cases.
Practice on FleetCode