Problem Description

You are given a 0-indexed integer array nums. Your task is to determine if this array can be made strictly increasing by removing exactly one element from it.

A strictly increasing array means that each element is strictly less than the next element. Formally, for an array to be strictly increasing, nums[i-1] < nums[i] must hold true for every index i where 1 <= i < nums.length.

The function should return true if:

• The array is already strictly increasing (in which case you can remove any element and still have at least one valid strictly increasing sequence), OR
• There exists exactly one element whose removal would make the remaining array strictly increasing

The function should return false if no single element removal can make the array strictly increasing.

For example:

• [1, 2, 10, 5, 7] → true (removing 10 gives [1, 2, 5, 7] which is strictly increasing)
• [2, 3, 1, 2] → false (no single removal can make it strictly increasing)
• [1, 2, 3] → true (already strictly increasing)

The solution works by finding the first position where the strictly increasing property is violated (where nums[i] >= nums[i+1]), then checking if removing either the element at position i or position i+1 results in a strictly increasing array. The helper function check(k) verifies if the array would be strictly increasing after removing the element at index k.

Intuition

When we need to make an array strictly increasing by removing exactly one element, the key insight is that there can be at most one "bad spot" where the increasing property is violated.

Think about it this way: if the array has two or more places where nums[i] >= nums[i+1], then we'd need to remove at least two elements to fix both violations, which exceeds our limit of removing exactly one element.

So our strategy becomes:

1. Scan through the array to find the first position where the strictly increasing property breaks (where nums[i] >= nums[i+1])
2. If no such position exists, the array is already strictly increasing, so we can remove any element and still maintain the property
3. If we find such a position i, the violation involves two elements: nums[i] and nums[i+1]

The crucial observation is that to fix this violation, we must remove either nums[i] or nums[i+1] - these are the only two candidates that could potentially resolve the issue at this spot. Removing any other element wouldn't fix the violation between these two consecutive elements.

Why only check these two positions? Because:

• If we remove nums[i], we're eliminating the larger element that's causing the violation
• If we remove nums[i+1], we're eliminating the smaller element that's breaking the increasing pattern

After removing one of these candidates, we need to verify that the entire remaining array is strictly increasing. We use a helper function that simulates the removal by skipping the element at index k and checking if all remaining elements form a strictly increasing sequence.

This approach is efficient because we only need to check at most two scenarios (removing element at position i or i+1), rather than trying to remove every possible element in the array.

Solution Approach

The implementation consists of two main parts: a helper function check and the main logic to find the violation point.

Helper Function check(k):

This function verifies if the array would be strictly increasing after removing the element at index k:

• Initialize pre = -inf to track the previous element (starting with negative infinity ensures the first element always satisfies the condition)
• Iterate through the array with enumerate to get both index and value
• Skip the element at index k (simulating its removal)
• For each non-skipped element, check if pre >= x. If true, the array isn't strictly increasing, so return False
• Update pre = x to track the current element for the next comparison
• If we complete the iteration without violations, return True

Main Algorithm:

1. Find the violation point:

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

   This loop advances i as long as the strictly increasing property holds. When the loop exits, i points to:

   • The last index if the array is already strictly increasing
   • The first position where nums[i] >= nums[i+1] (the violation)

2. Check two removal candidates:

   return check(i) or check(i + 1)

   We only need to check if removing either nums[i] or nums[i+1] results in a strictly increasing array:

   • check(i): Tests if removing the element at position i fixes the issue
   • check(i + 1): Tests if removing the element at position i+1 fixes the issue

   The function returns True if either removal works, False if neither works.

Time Complexity: O(n) where n is the length of the array. We traverse the array once to find the violation point, and the check function also runs in O(n). Since we call check at most twice, the overall complexity remains O(n).

Space Complexity: O(1) as we only use a constant amount of extra space for variables like i and pre.

Example Walkthrough

Let's walk through the example nums = [1, 2, 10, 5, 7] to illustrate the solution approach.

Step 1: Find the violation point

We start with i = 0 and check consecutive pairs:

• i = 0: Compare nums[0] (1) with nums[1] (2). Since 1 < 2, move to next position.
• i = 1: Compare nums[1] (2) with nums[2] (10). Since 2 < 10, move to next position.
• i = 2: Compare nums[2] (10) with nums[3] (5). Since 10 ≥ 5, we found our violation! Stop here.

So i = 2 is our violation point where the strictly increasing property breaks.

Step 2: Check removal candidates

Now we need to check if removing either nums[2] (10) or nums[3] (5) makes the array strictly increasing.

Check removing nums[2] (index i = 2):

• Start with pre = -inf
• Process index 0: value 1. Since -inf < 1, continue. Update pre = 1.
• Process index 1: value 2. Since 1 < 2, continue. Update pre = 2.
• Skip index 2 (simulating removal of 10)
• Process index 3: value 5. Since 2 < 5, continue. Update pre = 5.
• Process index 4: value 7. Since 5 < 7, continue. Update pre = 7.
• All checks passed! Return True.

Since check(2) returns True, we don't even need to check check(3). The function returns True because removing element at index 2 (the value 10) results in the strictly increasing array [1, 2, 5, 7].

Alternative scenario: If check(2) had returned False, we would then check check(3) to see if removing the element at index 3 (the value 5) would work instead.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums.

The algorithm first iterates through the array to find the first position i where nums[i] >= nums[i+1], which takes O(n) time in the worst case. Then it calls the check function at most twice - check(i) and check(i+1). Each call to check iterates through the entire array once (skipping one element), which takes O(n) time. Therefore, the total time complexity is O(n) + 2 * O(n) = O(n).

Space Complexity: O(1).

The algorithm only uses a constant amount of extra space for variables like i, pre, and loop counters. No additional data structures that scale with input size are created. The check function is defined within the method but doesn't create any space that depends on the input size - it only uses constant space for its local variables.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrectly Handling Multiple Violations

The Problem: A common mistake is trying to handle cases where there are multiple violations in the array. Beginners often write code that attempts to fix all violations or counts the number of violations:

# INCORRECT approach
def canBeIncreasing(self, nums: List[int]) -> bool:
    violations = 0
    for i in range(len(nums) - 1):
        if nums[i] >= nums[i + 1]:
            violations += 1
            # Try to "fix" by modifying values - WRONG!
            if i > 0 and nums[i - 1] >= nums[i + 1]:
                nums[i + 1] = nums[i]
    return violations <= 1

Why It Fails:

• Simply counting violations doesn't tell us if removing one element will fix the problem
• Modifying array values changes the problem constraints
• Example: [1, 2, 10, 5, 7] has one violation at index 2, but we need to know WHETHER removing index 2 OR index 3 will work

The Solution: Focus on finding just the FIRST violation point and only check those two specific removal candidates:

# Find FIRST violation only
i = 0
while i + 1 < len(nums) and nums[i] < nums[i + 1]:
    i += 1
# Only check these two specific removals
return check(i) or check(i + 1)

Pitfall 2: Not Considering Adjacent Elements After Removal

The Problem: When checking if removing an element works, forgetting that the elements before and after the removed element become adjacent:

# INCORRECT check function
def check(k):
    for i in range(len(nums)):
        if i == k:
            continue
        if i > 0 and i - 1 != k and nums[i - 1] >= nums[i]:
            return False
    return True

Why It Fails: This doesn't properly track the "previous" element after skipping. For example, with [1, 5, 3, 4]:

• If we remove index 1 (value 5), we need to check if 1 < 3 < 4
• The incorrect approach might miss comparing 1 with 3

The Solution: Use a separate variable to track the actual previous element in the resulting array:

def check(k):
    pre = -inf  # Track the actual previous element
    for i, x in enumerate(nums):
        if i == k:
            continue
        if pre >= x:  # Compare with tracked previous
            return False
        pre = x  # Update tracked previous
    return True

Pitfall 3: Edge Case with Already Strictly Increasing Arrays

The Problem: Not handling the case where the array is already strictly increasing:

# INCORRECT: Assumes there must be a violation
def canBeIncreasing(self, nums: List[int]) -> bool:
    for i in range(len(nums) - 1):
        if nums[i] >= nums[i + 1]:
            # Found violation, check removals
            return check(i) or check(i + 1)
    # Forgot to handle no violations case!
    return False  # WRONG!

Why It Fails: If the array is already strictly increasing (like [1, 2, 3, 4]), there are no violations. The function should return True because we can remove any element and still maintain a strictly increasing sequence.

The Solution: The correct approach handles this naturally by having i point to the last index when no violations are found:

i = 0
while i + 1 < len(nums) and nums[i] < nums[i + 1]:
    i += 1
# If no violation, i = len(nums) - 1
# check(len(nums) - 1) will return True for already increasing arrays
return check(i) or check(i + 1)