Remove One Element to Make the Array Strictly Increasing

Difficulty: Easy | Acceptance: 29.80% | Paid: No Topics: Array

Given a 0-indexed integer array nums, return true if it can be made strictly increasing by removing at most one element, or false otherwise.

An array nums is strictly increasing if nums[i] < nums[i+1] for all valid i.

Examples

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].

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 false is returned.

Example 3:

Input: nums = [1,1,1]
Output: false
Explanation: The result of removing any of the elements is [1,1], which is not strictly increasing.

Constraints

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

• Brute Force
• Greedy One-Pass

Examples

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].

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 false is returned.

Example 3:

Input: nums = [1,1,1]
Output: false
Explanation: The result of removing any of the elements is [1,1], which is not strictly increasing.

Constraints

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

Brute Force

Intuition We can try removing every element one by one and check if the resulting array is strictly increasing. If any removal works, we return true.

Steps

• Iterate through the array indices.
• For each index, create a new array excluding the element at that index.
• Check if the new array is strictly increasing.
• If any check passes, return true. If the loop finishes without success, return false.

class Solution:
    def canBeIncreasing(self, nums: list[int]) -> bool:
        n = len(nums)
        for i in range(n):
            temp = nums[:i] + nums[i+1:]
            if all(temp[j] < temp[j+1] for j in range(len(temp)-1)):
                return True
        return False

Complexity

• Time: O(n²)
• Space: O(n)
• Notes: Simple to implement but inefficient for large arrays.

Greedy One-Pass

Intuition We only need to find the first “dip” (where nums[i] >= nums[i+1]). If we find a dip, we have two choices: remove the element at i or the element at i+1. We check if either choice results in a strictly increasing array.

Steps

• Iterate through the array.
• If nums[i] >= nums[i+1], we found a violation.
• Check if the array is strictly increasing if we skip index i.
• Check if the array is strictly increasing if we skip index i+1.
• If either check passes, return true; otherwise, return false.
• If the loop completes without finding a violation, return true.

class Solution:
    def canBeIncreasing(self, nums: list[int]) -> bool:
        def is_increasing(arr):
            for i in range(len(arr) - 1):
                if arr[i] >= arr[i+1]:
                    return False
            return True

        for i in range(len(nums) - 1):
            if nums[i] >= nums[i+1]:
                # Try removing nums[i]
                if is_increasing(nums[:i] + nums[i+1:]):
                    return True
                # Try removing nums[i+1]
                if is_increasing(nums[:i+1] + nums[i+2:]):
                    return True
                return False
        return True

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Optimal solution with linear time complexity.