LeetCode 1909 - Remove One Element to Make the Array Strictly Increasing

The problem gives us a 0-indexed integer array nums and asks whether it is possible to make the array strictly increasing after removing exactly one element. A strictly increasing array means that every element must be greater than the previous one.

leetcodeeasyarray

LeetCode Problem 1909

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

The problem gives us a 0-indexed integer array nums and asks whether it is possible to make the array strictly increasing after removing exactly one element. A strictly increasing array means that every element must be greater than the previous one. Formally, for every valid index i, the condition nums[i - 1] < nums[i] must hold.

The important detail is that we are allowed to remove only one element. If the array is already strictly increasing, the answer is still true because we can remove any single element and the remaining sequence will remain strictly increasing.

The input is an integer array with length between 2 and 1000. Since the constraints are fairly small, even quadratic solutions would technically work, but the problem is designed to test whether we can reason about violations in the increasing order efficiently.

The expected output is a boolean value:

  • Return true if removing one element can produce a strictly increasing array.
  • Return false otherwise.

Several edge cases are important to recognize early:

  • Arrays that are already strictly increasing.
  • Arrays with duplicate values, since equal adjacent values violate strict increasing order.
  • Arrays with more than one violation, because one removal may not be enough.
  • Violations near the beginning or end of the array, where boundary checks become important.
  • Very short arrays, especially length 2, because removing one element always leaves a trivially increasing array.

For example:

  • [1,2,10,5,7] becomes increasing by removing 10.
  • [2,3,1,2] cannot be fixed with a single removal.
  • [1,1,1] still contains duplicates after any removal.

Approaches

Brute Force Approach

The brute-force solution tries removing every possible element one by one. For each removal:

  1. Create a new array without that element.
  2. Check whether the resulting array is strictly increasing.
  3. If any removal works, return true.

This approach is correct because it explicitly tests every valid removal possibility. Since the problem asks whether at least one removal can produce a strictly increasing array, exhaustive checking guarantees correctness.

However, this approach is inefficient because for every index we may need to scan the entire remaining array again. If the array has length n, we perform n checks, each costing O(n), resulting in O(n^2) time complexity.

Even though n <= 1000 is small enough for this to pass, we can do better.

Optimal Approach

The key insight is that a strictly increasing array can contain at most one violation if it is fixable by removing a single element.

A violation occurs when:

nums[i] >= nums[i + 1]

When we encounter such a violation, we have only two possible fixes:

  • Remove nums[i]
  • Remove nums[i + 1]

We do not need to actually remove elements from the array. Instead, we can simulate the decision by checking whether skipping one of the two elements preserves the increasing property.

If we encounter more than one violation, then one removal is insufficient, so we immediately return false.

This observation allows us to solve the problem in a single pass.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Try removing every element and validate the result
Optimal O(n) O(1) Count violations and determine whether one removal can fix them

Algorithm Walkthrough

  1. Initialize a counter called violations to track how many times the increasing order is broken.
  2. Traverse the array from left to right starting at index 1.
  3. For each index i, compare nums[i - 1] and nums[i].
  4. If nums[i - 1] < nums[i], the sequence is still strictly increasing at this position, so continue.
  5. Otherwise, we found a violation because the previous element is greater than or equal to the current one.
  6. Increment the violations counter. If the counter becomes greater than 1, immediately return false because removing only one element cannot fix multiple violations.
  7. When a violation is found, determine whether it can be fixed:

  • If i == 1, we can always remove the first element.

  • If i == len(nums) - 1, we can always remove the last element.

  • Otherwise, check these two possibilities:

  • Remove nums[i - 1], valid if:

nums[i - 2] < nums[i]
  • Remove nums[i], valid if:
nums[i - 1] < nums[i + 1]
  1. If neither removal option works, return false.
  2. If the traversal finishes successfully, return true.

Why it works

The algorithm works because every violation in a strictly increasing sequence must be resolved by removing one of the two elements involved in the violation. There are no other possibilities. By checking whether either local removal preserves the increasing property, we guarantee that the remaining sequence can still become valid. Since we allow only one removal, more than one violation immediately makes the task impossible.

Python Solution

from typing import List

class Solution:
    def canBeIncreasing(self, nums: List[int]) -> bool:
        violations = 0
        n = len(nums)

        for i in range(1, n):
            if nums[i - 1] >= nums[i]:
                violations += 1

                if violations > 1:
                    return False

                remove_previous = (
                    i == 1 or nums[i - 2] < nums[i]
                )

                remove_current = (
                    i == n - 1 or nums[i - 1] < nums[i + 1]
                )

                if not remove_previous and not remove_current:
                    return False

        return True

The implementation follows the exact logic described in the algorithm walkthrough.

The variable violations keeps track of how many ordering problems we encounter while scanning the array. During traversal, whenever nums[i - 1] >= nums[i], we know the strictly increasing property has been violated.

The code then checks whether removing either the previous element or the current element can repair the sequence locally. The condition:

nums[i - 2] < nums[i]

tests whether removing the previous element maintains increasing order.

The condition:

nums[i - 1] < nums[i + 1]

tests whether removing the current element maintains increasing order.

Boundary cases are handled carefully:

  • If the violation occurs at the beginning, removing the first element is always valid.
  • If the violation occurs at the end, removing the last element is always valid.

If neither option works, the function immediately returns False.

If the loop completes without finding more than one unfixable violation, the function returns True.

Go Solution

func canBeIncreasing(nums []int) bool {
    violations := 0
    n := len(nums)

    for i := 1; i < n; i++ {
        if nums[i-1] >= nums[i] {
            violations++

            if violations > 1 {
                return false
            }

            removePrevious := i == 1 || nums[i-2] < nums[i]
            removeCurrent := i == n-1 || nums[i-1] < nums[i+1]

            if !removePrevious && !removeCurrent {
                return false
            }
        }
    }

    return true
}

The Go implementation mirrors the Python solution closely. Since Go does not have Python style negative indexing, boundary checks must be performed explicitly before accessing neighboring elements.

Slices in Go are naturally dynamic references to arrays, so no additional copying is needed. Integer overflow is not a concern because the constraints are very small.

Worked Examples

Example 1

nums = [1,2,10,5,7]
i nums[i - 1] nums[i] Violation? violations Action
1 1 2 No 0 Continue
2 2 10 No 0 Continue
3 10 5 Yes 1 Check removals
4 5 7 No 1 Continue

At index 3:

  • Remove 10:
2 < 5

Valid.

The algorithm returns true.

Example 2

nums = [2,3,1,2]
i nums[i - 1] nums[i] Violation? violations Action
1 2 3 No 0 Continue
2 3 1 Yes 1 Check removals

At index 2:

  • Remove 3:
2 < 1

False.

  • Remove 1:
3 < 2

False.

Neither removal works, so the algorithm returns false.

Example 3

nums = [1,1,1]
i nums[i - 1] nums[i] Violation? violations Action
1 1 1 Yes 1 Check removals

At index 1:

  • Removing first 1 still leaves [1,1]
  • Removing second 1 still leaves [1,1]

Neither option creates a strictly increasing array, so the algorithm returns false.

Complexity Analysis

Measure Complexity Explanation
Time O(n) The array is scanned exactly once
Space O(1) Only a few variables are used

The algorithm performs a single linear traversal through the array. Every iteration does constant-time comparisons and bookkeeping, so the total running time is proportional to the array length. No additional data structures proportional to input size are allocated, resulting in constant auxiliary space usage.

Test Cases

sol = Solution()

assert sol.canBeIncreasing([1,2,10,5,7]) == True   # remove middle violating element
assert sol.canBeIncreasing([2,3,1,2]) == False     # impossible with one removal
assert sol.canBeIncreasing([1,1,1]) == False       # duplicates remain after removal

assert sol.canBeIncreasing([1,2,3,4]) == True      # already strictly increasing
assert sol.canBeIncreasing([1,2]) == True          # smallest valid increasing case
assert sol.canBeIncreasing([2,1]) == True          # remove one element from size 2

assert sol.canBeIncreasing([1,2,3,2,4]) == True   # remove interior violating element
assert sol.canBeIncreasing([10,1,2,3]) == True    # remove first element
assert sol.canBeIncreasing([1,2,3,0]) == True     # remove last element

assert sol.canBeIncreasing([1,2,5,3,4]) == True   # remove 5
assert sol.canBeIncreasing([1,2,3,2,1]) == False  # multiple violations

assert sol.canBeIncreasing([1,2,2,3]) == True     # remove one duplicate
assert sol.canBeIncreasing([1,1,2,3]) == True     # remove first duplicate
assert sol.canBeIncreasing([3,2,1]) == False      # descending array

assert sol.canBeIncreasing([1,5,3,4,2,6]) == False  # more than one violation
Test Why
[1,2,10,5,7] Standard removable violation
[2,3,1,2] No valid single removal
[1,1,1] Duplicate-heavy failure case
[1,2,3,4] Already strictly increasing
[1,2] Smallest increasing array
[2,1] Size two always fixable
[1,2,3,2,4] Violation in middle
[10,1,2,3] Remove first element
[1,2,3,0] Remove last element
[1,2,5,3,4] Remove large middle element
[1,2,3,2,1] Multiple violations
[1,2,2,3] Remove duplicate
[1,1,2,3] Duplicate at beginning
[3,2,1] Strictly decreasing
[1,5,3,4,2,6] Requires more than one removal

Edge Cases

One important edge case is when the array is already strictly increasing. A naive implementation might incorrectly assume that exactly one problematic element must exist. However, the problem explicitly states that already increasing arrays should return true. Our implementation naturally handles this because no violations are detected during traversal.

Another important edge case involves duplicate values such as [1,2,2,3]. Since the condition requires strict increasing order, equal adjacent elements are invalid. Some implementations mistakenly use > instead of >= when detecting violations. Our solution correctly identifies duplicates as violations because it checks:

nums[i - 1] >= nums[i]

Boundary violations are also tricky. Consider [10,1,2,3] or [1,2,3,0]. In these cases, the removable element is at the beginning or end of the array. Accessing neighbors carelessly can cause index errors. Our implementation handles this safely with explicit checks:

i == 1

and

i == n - 1

These conditions guarantee that edge removals are evaluated correctly without invalid indexing.