Code Implementation

class Solution:
    def canBeIncreasing(self, nums):
        n = len(nums)
        removed = 0
        for i in range(1, n):
            if nums[i] <= nums[i - 1]:
                if removed == 1:
                    return False
                removed += 1
                # Remove nums[i-1] if possible, else nums[i]
                if i == 1 or nums[i] > nums[i - 2]:
                    continue
                elif i + 1 == n or nums[i + 1] > nums[i - 1]:
                    nums[i] = nums[i - 1]
                else:
                    return False
        return True
      

class Solution {
public:
    bool canBeIncreasing(vector<int>& nums) {
        int n = nums.size(), removed = 0;
        for (int i = 1; i < n; ++i) {
            if (nums[i] <= nums[i-1]) {
                if (++removed > 1) return false;
                if (i == 1 || nums[i] > nums[i-2]) continue;
                else if (i+1 == n || nums[i+1] > nums[i-1]) nums[i] = nums[i-1];
                else return false;
            }
        }
        return true;
    }
};
      

class Solution {
    public boolean canBeIncreasing(int[] nums) {
        int removed = 0, n = nums.length;
        for (int i = 1; i < n; i++) {
            if (nums[i] <= nums[i - 1]) {
                if (removed == 1) return false;
                removed++;
                if (i == 1 || nums[i] > nums[i - 2]) continue;
                else if (i + 1 == n || nums[i + 1] > nums[i - 1]) nums[i] = nums[i - 1];
                else return false;
            }
        }
        return true;
    }
}
      

var canBeIncreasing = function(nums) {
    let removed = 0, n = nums.length;
    for (let i = 1; i < n; i++) {
        if (nums[i] <= nums[i - 1]) {
            if (removed === 1) return false;
            removed++;
            if (i === 1 || nums[i] > nums[i - 2]) continue;
            else if (i + 1 === n || nums[i + 1] > nums[i - 1]) nums[i] = nums[i - 1];
            else return false;
        }
    }
    return true;
};
      

Problem Description

Given an array of integers nums, determine if it is possible to make the array strictly increasing by removing exactly one element. An array is strictly increasing if for every index i (1 ≤ i < n), nums[i - 1] < nums[i] holds true.

• You must remove exactly one element, or none if the array is already strictly increasing.
• Each element can only be removed once (no reusing or multiple removals).
• The goal is to return true if it's possible to achieve a strictly increasing sequence by removing one element, otherwise return false.

Example: For nums = [1,2,10,5,7], removing 10 or 5 results in a strictly increasing array.

Thought Process

The first idea that comes to mind is to try removing each element one by one and check if the resulting array is strictly increasing. However, this brute-force approach is inefficient, especially for large arrays.

We can optimize by observing that we only care about the first place where the strictly increasing property is violated. If we find more than one such violation, it's impossible to fix the array by removing just one element.

When we find a violation (i.e., nums[i] <= nums[i-1]), we have two choices:

• Remove nums[i-1], if removing it would restore the strictly increasing order.
• Remove nums[i], if removing it would restore the strictly increasing order.

This insight allows us to scan the array just once and decide in-place whether a single removal is sufficient.

Solution Approach

• Step 1: Initialize a counter (e.g., removed) to track how many elements we've "removed" (or needed to remove).
• Step 2: Iterate through the array from the second element to the end.
• Step 3: For each element, check if nums[i] <= nums[i-1]. If not, continue.
• Step 4: If a violation is found:
  • Increment the removed counter. If it's more than 1, return false.
  • Check if removing nums[i-1] works:
    • If i == 1 (removing the first element), or nums[i] > nums[i-2], then it's safe to "remove" nums[i-1].
    • Else, if removing nums[i] (i.e., nums[i+1] > nums[i-1]), then we can "remove" nums[i] by setting nums[i] = nums[i-1] (for the purpose of further checks).
    • If neither removal works, return false.
• Step 5: If the loop completes with at most one removal, return true.

This approach ensures that we only ever attempt to "remove" one element and check the minimum needed to restore the strictly increasing property.

Example Walkthrough

Let's walk through the example nums = [1, 2, 10, 5, 7]:

1. Start with removed = 0.
2. Compare 2 > 1: OK.
3. Compare 10 > 2: OK.
4. Compare 5 <= 10: Violation found at index 3.
   • Try removing 10: Is 5 > 2? Yes. "Remove" 10. Continue.
5. Compare 7 > 5: OK.
6. End of array, only one removal needed. Return true.

If we had nums = [2, 3, 1, 2]:

• Compare 3 > 2: OK.
• Compare 1 <= 3: Violation. Try removing 3: 1 > 2? No. Try removing 1: 2 > 3? No. Can't fix, return false.

Time and Space Complexity

• Brute-force approach: For each element, remove it and check if the rest is strictly increasing. This is O(n^2) time and O(n) space (for array copies).
• Optimized approach (above): We scan the array once, so time complexity is O(n). Space complexity is O(1) since we only use a few variables and (optionally) modify the array in-place.

The optimized solution is much more efficient, especially for large arrays.

Summary

The key insight is that we only need to consider the first violation of the strictly increasing property and check if removing either of the two involved elements will fix the sequence. By carefully checking the neighbors, we can determine in linear time if the array can be made strictly increasing by removing just one element. This approach is efficient, elegant, and easy to implement.