#1909

Easy

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Remove One Element to Make the Array Strictly Increasing

Determine if removing a single element from an array can make it strictly increasing, using a careful index check approach.

array

Problem Statement

Given a 0-indexed array of integers nums, determine whether it is possible to remove exactly one element so that the remaining array is strictly increasing. Return true if possible, or false otherwise. An array is strictly increasing if every element is smaller than the next element.

For example, if nums = [1,2,10,5,7], removing the element 10 at index 2 results in [1,2,5,7], which is strictly increasing. If no single removal can achieve a strictly increasing array, the function should return false. Arrays of length 2 or more should be handled efficiently.

Examples

Example 1

Input: nums = [1,2,10,5,7]

Output: true

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

[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

The result of removing any element is [1,1]. [1,1] is not strictly increasing, so return false.

Constraints

2 <= nums.length <= 1000
1 <= nums[i] <= 1000

Solution Approach

Single Pass Violation Detection

Iterate through nums to locate the first pair where nums[i] <= nums[i-1]. Identify this as a potential removal point and consider removing nums[i] or nums[i-1] to restore strict increase.

Test Array After Removal

For each candidate removal index, construct the array without that element and check if the resulting array is strictly increasing. If any removal produces a valid array, return true immediately.

Early Return and Optimization

If the array is already strictly increasing, return true without further checks. Avoid unnecessary full array copies by using pointer comparisons or simple linear scans to verify increasing order after potential removals.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The algorithm scans the array once to detect violations and may scan again for at most two candidate removals, giving a time complexity of O(n). Space complexity is O(1) if we check in-place or O(n) if constructing new arrays for removal checks.

What Interviewers Usually Probe

Expect you to identify the minimal disruption causing non-increasing order.
Look for handling edge cases like consecutive equal elements or arrays of length 2.
Watch for correct identification of which element to remove when multiple violations exist.

Common Pitfalls or Variants

Common pitfalls

Removing the wrong element at a violation can lead to false negatives.
Assuming multiple removals are allowed when only one is permitted.
Failing to handle arrays that are already strictly increasing.

Follow-up variants

Check if removing up to k elements can make the array strictly increasing.
Return the index of the element whose removal fixes the sequence, if possible.
Determine if adding an element can make the array strictly increasing instead of removing.

FAQ

What is the best approach to solve Remove One Element to Make the Array Strictly Increasing?

Use a single pass to find the first violation, then test removing either the violating element or the previous one to see if the array becomes strictly increasing.

Can I remove more than one element in this problem?

No, the problem specifically allows removing exactly one element to achieve a strictly increasing array.

How do I handle arrays that are already strictly increasing?

If the array is already strictly increasing, return true immediately without testing any removal.

What should I do if the array has duplicate consecutive elements?

Duplicate consecutive elements violate strict increase, so removing one of the duplicates may fix the array if only one removal is needed.

What is the time complexity for this array-driven solution strategy?

The solution uses at most two linear scans over the array, resulting in O(n) time complexity and O(1) extra space if done in-place.

terminal

Solution

Solution 1: Traversal

We can traverse the array to find the first position $i$ where $\textit{nums}[i] < \textit{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 $\textit{true}$; otherwise, we return $\textit{false}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def canBeIncreasing(self, nums: List[int]) -> bool:
        def check(k: int) -> bool:
            pre = -inf
            for i, x in enumerate(nums):
                if i == k:
                    continue
                if pre >= x:
                    return False
                pre = x
            return True

        i = 0
        while i + 1 < len(nums) and nums[i] < nums[i + 1]:
            i += 1
        return check(i) or check(i + 1)

Continue Practicing

#1911 maximum alternating subsequence sum #1906 minimum absolute difference queries #1912 design movie rental system