Remove One Element to Make the Array Strictly Increasing

When we traverse the list and find a number which is not larger than the previous one, we have two options: either remove the current number, or the previous number. We should always prefer removing the current number, because the number before the previous one might be less than the current number. Therefore, we remove the previous number only when it is not less than the current one.

We use a variable removed to record if we have removed a number. If we find a second number that requires removal, we return False. If we traverse the whole list without finding a second removal, we return True.

Here is the Python code that represents this approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def canBeIncreasing(self, nums: List[int]) -> bool:
        removed = False
        for i in range(1, len(nums)):
            if nums[i] <= nums[i - 1]:
                if removed:
                    return False
                if i > 1 and nums[i] <= nums[i - 2]:
                    nums[i] = nums[i - 1]
                removed = True
        return True

This code checks if a number is less than or equal to the previous one. If yes, we need to consider removing a number. If we have already removed a number (tracked by the variable removed), we return False because we can only remove exactly one number. Otherwise, we check if the current number is less than or equal to the number before the previous one, if yes, we remove the previous one by replacing it with the current one. Finally, we mark removed as True.

In each iteration, the operation is done in constant time, hence the total time complexity of the solution is O(n), where n is the length of nums. The space complexity is O(1) because we only use a few variables to track the information.

The basic building blocks are Neighbor Comparison and Flagging.

In this problem, we are using a “Neighbor Comparison” mechanism where we are constantly comparing an element with its previous neighbor in the array. This helps us detect any anomalies in the strictly increasing order.

The “Flagging” mechanism comes into play when we encounter an anomaly. The flag (in this case, the removed variable) is used to keep track if we have removed an element or not. If we have already removed an element and we encounter another anomaly, we know that we cannot make the array strictly increasing by removing exactly one element, so we return False.

These building blocks are fundamental in solving a wide range of array-based problems. Understanding and recognizing when to use them is crucial for problem-solving in coding interviews or competitive programming.

Q&A

Can someone tell me why this code in C++ is showing time limit exceeded it is O(n) then also ?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

bool canBeIncreasing(vector & nums) {
  int x = nums.size();
  for (int i = 0; i < nums.size() - 1;) {
    if (nums.at(i) >= nums.at(i + 1)) {
      if (i != 0) {
        if (nums.at(i - 1) <= nums.at(i) && nums.at(i - 1) >= nums.at(i + 1)) {
          nums.erase(nums.begin() + i + 1);
        } else {
          nums.erase(nums.begin() + i);
        }
      }
      int y = nums.size();
      if (x - y > 1) {
        return false;
      }
    } else {
      i++;
    }
  }
  return true;
}

Although your code seems to have a linear complexity O(n) due to the single loop, it actually has a time complexity of O(n^2) because of the nums.erase(nums.begin() + i); operation.

In C++, erasing an element from a vector involves shifting all the elements after it to fill the gap, which is an O(n) operation. So when you’re doing this inside a loop that also runs in O(n), your overall time complexity becomes O(n^2).

That’s why your code is exceeding the time limit, it’s not as efficient as it seems at first glance.

A better approach would be to not alter the original array by erasing elements, but instead count the number of anomalies (pairs of elements where nums[i] >= nums[i+1]) and also check if it’s possible to avoid each anomaly by comparing nums[i-1] and nums[i+1]. This will result in an O(n) time complexity without the hidden costs.

We iterate over the array, count anomalies, and check if they can be fixed by changing either the current or the previous number.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include<vector>
using namespace std;

class Solution {
public:
    bool canBeIncreasing(vector<int>& nums) {
        int anomalyCount = 0;
        for (int i = 1; i < nums.size() && anomalyCount <= 1; i++) {
            if (nums[i - 1] >= nums[i]) {
                anomalyCount++;
                if (i > 1 && nums[i - 2] >= nums[i]) {
                    nums[i] = nums[i - 1]; // Try changing the current number
                } else {
                    nums[i - 1] = nums[i]; // Try changing the previous number
                }
            }
        }
        return anomalyCount <= 1;
    }
};

This code increments anomalyCount whenever it finds a pair of numbers out of order. It tries to fix the anomaly by replacing the current number with the previous one if the one before the previous is also larger than the current. Otherwise, it replaces the previous number with the current. At the end, it checks if there was more than one anomaly, returning false if so, true otherwise. This guarantees that we only change one number at most.

I wrote a code in c++ and this is showing runtime error if anyone can tell why it is showing runtime error. It will be very helpful for me my code :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
  public: bool canBeIncreasing(vector & nums) {
    int count = 0, size = sizeof(nums);
    for (int i = 1; i < size - 1; i++) {
      if (nums[i] > nums[i + 1] || nums[i - 1] > nums[i]) {
        count++;
      }

    }
    if (count > 1) {
      return false;
    }
    return true;
  }

};

The runtime error in your code is likely due to the usage of sizeof(nums). In C++, sizeof doesn’t give you the size of the vector, it gives you the size of the vector object itself, which is not what you want. You should use nums.size() instead to get the number of elements in the vector.

Additionally, your condition inside the loop seems off, you’re checking nums[i] > nums[i+1] while your loop runs till i < size-1, this would cause an out-of-bounds error.

Here is the corrected version of your code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    bool canBeIncreasing(vector<int>& nums) {
        int count=0;
        int size=nums.size();  // use .size() method
        for (int i = 1; i < size-1; i++)  // loop until size-1
        {
            if (nums[i] <= nums[i+1] && nums[i-1] < nums[i])
            {
                continue;
            }
            count++;
        }
        if (count > 1)
        {
            return false;
        }
        return true;
    }
};

But please note, this code won’t work as expected for the problem statement. The problem requires that you ensure the sequence can be strictly increasing by modifying at most one element. The condition inside your for-loop doesn’t cater to this requirement. You should consider the explanation given earlier for a correct approach.