# Remove One Element to Make the Array Strictly Increasing
**Difficulty:** EASY
[External](https://leetcode.com/problems/remove-one-element-to-make-the-array-strictly-increasing)
Canonical: https://scaleengineer.com/dsa/problems/remove-one-element-to-make-the-array-strictly-increasing
**Data structures:** Array
**Companies:** [eBay](https://scaleengineer.com/companies/ebay)
---
## Problem
Given a **0-indexed** integer array `nums`, return `true` _if it can be made **strictly increasing** after removing **exactly one** element, or_ `false` _otherwise. If the array is already strictly increasing, return_ `true`.

The array `nums` is **strictly increasing** if `nums[i - 1] < nums[i]` for each index `(1 <= i < nums.length).`

**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].
[1,2,5,7] is strictly increasing, so return true.

**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 return false.

**Example 3:**

**Input:** nums = [1,1,1]
**Output:** false
**Explanation:** The result of removing any element is [1,1].
[1,1] is not strictly increasing, so return false.

**Constraints:**

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

# Approaches
## Brute Force Simulation
This approach directly simulates the process described in the problem. We iterate through each element of the array, and for each element, we hypothetically remove it and then check if the remaining part of the array is strictly increasing.
**Time:** O(N^2), where N is the number of elements in `nums`. The outer loop runs N times. Inside this loop, creating the temporary list takes O(N) time, and checking if it's increasing takes another O(N) time, leading to a total of N * O(N) = O(N^2). · **Space:** O(N), where N is the number of elements in `nums`. This space is used to store the temporary list in each iteration.
**Pros:** Simple to understand and implement.; Directly follows the logic of the problem statement.
**Cons:** Inefficient in terms of time complexity due to nested loops.; Requires extra space proportional to the input size to create temporary arrays.
### Explanation
We can use a loop that iterates from `i = 0` to `n-1`, where `n` is the length of the array. In each iteration, `i` represents the index of the element to be removed.

Inside the loop, we construct a new temporary array (or list) that contains all elements of the original array except the one at index `i`. After constructing the temporary array, we check if it is strictly increasing. This can be done with another loop that iterates through the temporary array, comparing each element with its predecessor.

If we find that a temporary array is strictly increasing, it means we've found a valid removal. We can immediately return `true`.

If the outer loop completes without finding any such valid removal, it means it's impossible to make the array strictly increasing by removing one element. In this case, we return `false`.

This also correctly handles the case where the array is already strictly increasing. For example, if `nums = [1, 2, 3]`, removing the last element `3` results in `[1, 2]`, which is strictly increasing, so the function will return `true`.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean canBeIncreasing(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            // Create a temporary list without the element at index i
            List<Integer> tempList = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    tempList.add(nums[j]);
                }
            }

            // Check if the temporary list is strictly increasing
            boolean isIncreasing = true;
            for (int k = 1; k < tempList.size(); k++) {
                if (tempList.get(k) <= tempList.get(k - 1)) {
                    isIncreasing = false;
                    break;
                }
            }

            if (isIncreasing) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
- Loop through each index `i` from `0` to `nums.length - 1`.
- In each iteration, `i` represents the index of the element to be removed.
- Create a new list, `tempList`.
- Loop through each index `j` from `0` to `nums.length - 1`.
- If `i != j`, add `nums[j]` to `tempList`.
- Check if `tempList` is strictly increasing. To do this, loop from `k = 1` to `tempList.size() - 1` and check if `tempList.get(k) <= tempList.get(k-1)`. If this condition is met, the list is not strictly increasing.
- If `tempList` is found to be strictly increasing, return `true`.
- If the outer loop finishes without finding a valid removal, return `false`.

## Optimized Single Pass
This optimal approach avoids the O(N^2) complexity by performing a single pass through the array. The key insight is that for the condition to be met, there can be at most one "violation" (where `nums[i] <= nums[i-1]`). We can find this violation and check if removing either of the two conflicting elements resolves the issue locally.
**Time:** O(N), where N is the number of elements in `nums`. We perform a single pass through the array to count violations. · **Space:** O(1), as we only use a few variables to keep track of violations and indices, regardless of the input size.
**Pros:** Highly efficient with linear time complexity.; Space-efficient, using only a constant amount of extra space.
**Cons:** The logic can be slightly more complex to reason about compared to the direct simulation.
### Explanation
The core idea is that if the array can be made strictly increasing by removing one element, there can be at most one index `i` where `nums[i] <= nums[i-1]`. If there are two or more such "dips", we would need to remove at least two elements, so we can immediately return `false`.

We iterate through the array once to find the number of violations and the index of the last violation.

- If we find **zero violations**, the array is already strictly increasing, so we return `true`.
- If we find **more than one violation**, it's impossible to fix the array by removing only one element, so we return `false`.
- If we find **exactly one violation** at index `p` (i.e., `nums[p] <= nums[p-1]`), we have two potential fixes:
  1.  **Remove `nums[p-1]`**: The array becomes `..., nums[p-2], nums[p], ...`. This is a valid fix if `nums[p-2] < nums[p]`. We must also consider the edge case where `p-1` is the first element of the array (`p=1`), in which case this removal is always a valid local fix.
  2.  **Remove `nums[p]`**: The array becomes `..., nums[p-1], nums[p+1], ...`. This is a valid fix if `nums[p-1] < nums[p+1]`. We must also consider the edge case where `p` is the last element of the array, in which case this removal is always a valid local fix.

If either of these two fixes works, we can return `true`. If the single violation cannot be fixed by either removal, we return `false`.

```java
class Solution {
    public boolean canBeIncreasing(int[] nums) {
        int violations = 0;
        int p = -1;
        int n = nums.length;

        for (int i = 1; i < n; i++) {
            if (nums[i] <= nums[i - 1]) {
                violations++;
                p = i;
            }
        }

        if (violations == 0) {
            return true;
        }

        if (violations > 1) {
            return false;
        }

        // At this point, violations == 1. The violation is at index p.
        // This means nums[p] <= nums[p-1]

        // Case 1: Try removing nums[p-1]. The sequence becomes ..., nums[p-2], nums[p], ...
        // This is valid if p is 1 (i.e., we remove nums[0]) or if nums[p-2] < nums[p].
        if (p == 1 || nums[p - 2] < nums[p]) {
            return true;
        }

        // Case 2: Try removing nums[p]. The sequence becomes ..., nums[p-1], nums[p+1], ...
        // This is valid if p is the last index or if nums[p-1] < nums[p+1].
        if (p == n - 1 || nums[p - 1] < nums[p + 1]) {
            return true;
        }

        return false;
    }
}
```
### Algorithm
- Initialize a counter `violations = 0` and an index `p = -1`.
- Loop through the array from `i = 1` to `n-1`.
- If `nums[i] <= nums[i-1]`, increment `violations` and store the current index `i` in `p`.
- After the loop, check the value of `violations`:
  - If `violations == 0`, the array is already strictly increasing. Return `true`.
  - If `violations > 1`, more than one removal is needed. Return `false`.
  - If `violations == 1`, we have a single dip at index `p`. We can fix this if either removing `nums[p]` or `nums[p-1]` results in a valid sequence.
    - Removing `nums[p-1]` is valid if `p == 1` (it's the first element) or if `nums[p-2] < nums[p]`.
    - Removing `nums[p]` is valid if `p == n-1` (it's the last element) or if `nums[p-1] < nums[p+1]`.
- If either of the conditions for `violations == 1` is met, return `true`. Otherwise, return `false`.

# Solutions
### CSharp

```csharp
public class Solution { public bool CanBeIncreasing ( int [] nums ) { int n = nums . Length ; bool check ( int k ) { int pre = 0 ; for ( int i = 0 ; i < n ; ++ i ) { if ( i == k ) { continue ; } if ( pre >= nums [ i ]) { return false ; } pre = nums [ i ]; } return true ; } int i = 0 ; while ( i + 1 < n && nums [ i ] < nums [ i + 1 ]) { ++ i ; } return check ( i ) || check ( i + 1 ); } }
```

### Java

```java
class Solution {
public
  boolean canBeIncreasing(int[] nums) {
    int i = 1, n = nums.length;
    for (; i < n && nums[i - 1] < nums[i]; ++i)
      ;
    return check(nums, i - 1) || check(nums, i);
  }
private
  boolean check(int[] nums, int i) {
    int prev = Integer.MIN_VALUE;
    for (int j = 0; j < nums.length; ++j) {
      if (i == j) {
        continue;
      }
      if (prev >= nums[j]) {
        return false;
      }
      prev = nums[j];
    }
    return true;
  }
}

```

### CPP

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

```

### Python

```python
class Solution:
    def canBeIncreasing(self, nums: List[int]) -> bool: def check(nums, i): prev = - inf for j, num in enumerate(nums): if i == j: continue if prev >= nums[j]: return False prev = nums[j] return True i, n = 1, len(nums) while i < n and nums[i - 1] < nums[i]: i += 1 return check(nums, i - 1) or check(nums, i)

```