# Count the Number of Incremovable Subarrays II
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-the-number-of-incremovable-subarrays-ii)
Canonical: https://scaleengineer.com/dsa/problems/count-the-number-of-incremovable-subarrays-ii
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [IBM](https://scaleengineer.com/companies/ibm), [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
You are given a **0-indexed** array of **positive** integers `nums`.

A subarray of `nums` is called **incremovable** if `nums` becomes **strictly increasing** on removing the subarray. For example, the subarray `[3, 4]` is an incremovable subarray of `[5, 3, 4, 6, 7]` because removing this subarray changes the array `[5, 3, 4, 6, 7]` to `[5, 6, 7]` which is strictly increasing.

Return _the total number of **incremovable** subarrays of_ `nums`.

**Note** that an empty array is considered strictly increasing.

A **subarray** is a contiguous non-empty sequence of elements within an array.

**Example 1:**

**Input:** nums = [1,2,3,4]
**Output:** 10
**Explanation:** The 10 incremovable subarrays are: [1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3], [2,3,4], and [1,2,3,4], because on removing any one of these subarrays nums becomes strictly increasing. Note that you cannot select an empty subarray.

**Example 2:**

**Input:** nums = [6,5,7,8]
**Output:** 7
**Explanation:** The 7 incremovable subarrays are: [5], [6], [5,7], [6,5], [5,7,8], [6,5,7] and [6,5,7,8].
It can be shown that there are only 7 incremovable subarrays in nums.

**Example 3:**

**Input:** nums = [8,7,6,6]
**Output:** 3
**Explanation:** The 3 incremovable subarrays are: [8,7,6], [7,6,6], and [8,7,6,6]. Note that [8,7] is not an incremovable subarray because after removing [8,7] nums becomes [6,6], which is sorted in ascending order but not strictly increasing.

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 109`

# Approaches
## Brute Force Approach
This approach iterates through all possible subarrays `nums[i..j]` and, for each one, checks if removing it results in a strictly increasing array. To avoid re-computing whether the remaining parts are sorted for each subarray, we can precompute which prefixes and suffixes of the original array are strictly increasing. This brings the check for each subarray down to O(1), but the overall complexity remains quadratic due to iterating through all subarrays.
**Time:** O(n^2). The nested loops iterate through all `n * (n + 1) / 2` possible subarrays, and the check inside is O(1). · **Space:** O(1). The implementation shown avoids explicit precomputation arrays by finding the bounds `l` and `r`, thus using constant extra space.
**Pros:** Conceptually simple and directly follows the problem definition.; Easier to implement correctly compared to more optimized solutions.
**Cons:** The time complexity of O(n^2) is too slow for the given constraints (n <= 10^5) and will result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
A subarray `nums[i..j]` is considered 'incremovable' if the array formed by concatenating the prefix `nums[0...i-1]` and the suffix `nums[j+1...n-1]` is strictly increasing. This holds true if three conditions are met:

1.  The prefix `nums[0...i-1]` is strictly increasing.
2.  The suffix `nums[j+1...n-1]` is strictly increasing.
3.  If both the prefix and suffix are non-empty, the last element of the prefix must be strictly less than the first element of the suffix (i.e., `nums[i-1] < nums[j+1]`).

To implement this efficiently, we first precompute boolean arrays that tell us if `nums[0...k]` and `nums[k...n-1]` are sorted for all `k`. Then, we can loop through all `O(n^2)` subarrays and check these conditions in constant time.

```java
class Solution {
    public long incremovableSubarrayCount(int[] nums) {
        int n = nums.length;
        long count = 0;

        // Find the longest strictly increasing prefix
        int l = 0;
        while (l + 1 < n && nums[l] < nums[l + 1]) {
            l++;
        }

        // Find the longest strictly increasing suffix
        int r = n - 1;
        while (r > 0 && nums[r - 1] < nums[r]) {
            r--;
        }

        for (int i = 0; i < n; i++) { // start index of subarray to remove
            for (int j = i; j < n; j++) { // end index of subarray to remove
                // Check if prefix nums[0...i-1] is sorted
                boolean prefixOk = (i - 1 <= l);
                // Check if suffix nums[j+1...n-1] is sorted
                boolean suffixOk = (j + 1 >= r);

                if (prefixOk && suffixOk) {
                    boolean connectionOk = true;
                    if (i > 0 && j < n - 1) {
                        if (nums[i - 1] >= nums[j + 1]) {
                            connectionOk = false;
                        }
                    }
                    if (connectionOk) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}
```
### Algorithm
*   **Precomputation:**
    1.  Create a boolean array `is_prefix_sorted` of size `n`. `is_prefix_sorted[i]` will be true if the subarray `nums[0...i]` is strictly increasing.
    2.  Create a boolean array `is_suffix_sorted` of size `n`. `is_suffix_sorted[j]` will be true if the subarray `nums[j...n-1]` is strictly increasing.
    3.  These arrays can be filled in O(n) time.
*   **Main Logic:**
    1.  Initialize a counter `count` to 0.
    2.  Iterate through all possible start indices `i` from `0` to `n`.
    3.  For each `i`, iterate through all possible end indices `j` from `i-1` to `n-1`.
        *   The subarray to be removed is `nums[i...j]`. If `i > j`, the removed subarray is empty, which is not allowed.
    4.  For each non-empty subarray `nums[i...j]`:
        *   Check if the prefix `nums[0...i-1]` is strictly increasing using the precomputed array.
        *   Check if the suffix `nums[j+1...n-1]` is strictly increasing using the precomputed array.
        *   If both prefix and suffix are non-empty (i.e., `i > 0` and `j < n-1`), check if `nums[i-1] < nums[j+1]`.
        *   If all conditions are met, increment the `count`.
*   **Return `count`**.

## Two Pointers with Binary Search
A more efficient approach avoids checking every subarray. We can observe that for a subarray `nums[i..j]` to be incremovable, the prefix `nums[0..i-1]` must itself be a strictly increasing prefix of `nums`, and `nums[j+1..n-1]` must be a strictly increasing suffix. This observation allows us to limit our search space.

We first find the longest strictly increasing prefix (ending at index `l`) and the longest strictly increasing suffix (starting at index `r`). Then, we iterate through all valid prefixes (which are prefixes of `nums[0..l]`) and for each, we count how many valid suffixes (which are suffixes of `nums[r..n-1]`) can be concatenated to it. This count can be done efficiently using binary search because the suffix `nums[r..n-1]` is sorted.
**Time:** O(n log n). Finding `l` and `r` takes O(n). The main loop runs up to `n` times, and each iteration performs a binary search on a portion of the array, which takes O(log n) time. · **Space:** O(1), as we only use a few variables to store indices and the count.
**Pros:** Much more efficient than the brute-force approach.; Correctly solves the problem within the time limits for the given constraints.
**Cons:** While it passes the constraints, it's not the most optimal solution.; The repeated binary searches introduce a logarithmic factor to the time complexity.
### Explanation
The core idea is to count pairs of valid prefixes and suffixes that can form a strictly increasing sequence when concatenated. A prefix `nums[0...i-1]` is valid if `i-1 <= l`, and a suffix `nums[j+1...n-1]` is valid if `j+1 >= r`.

We can systematically count the total number of incremovable subarrays by considering two disjoint cases:
1.  **Removing a subarray that leaves an empty prefix:** This means removing `nums[0...j]`. The remaining part `nums[j+1...n-1]` must be a valid strictly increasing suffix. This is true if `j+1 >= r`. The number of such `j`'s is `n-r+1`.
2.  **Removing a subarray that leaves a non-empty prefix:** The prefix must be `nums[0...i]` for some `0 <= i <= l`. For each such prefix, we need to count the number of valid suffixes `nums[p...n-1]` (`p >= r`) such that `nums[i] < nums[p]`. Since `nums[r...n-1]` is sorted, we can find the first valid `p` using binary search. If `p` is the first index, then all suffixes starting from `p` to `n-1` are valid, plus the empty suffix. This gives `(n-p) + 1` possibilities for each `i`.

```java
class Solution {
    public long incremovableSubarrayCount(int[] nums) {
        int n = nums.length;
        int l = 0;
        while (l + 1 < n && nums[l] < nums[l + 1]) {
            l++;
        }

        if (l == n - 1) {
            return (long)n * (n + 1) / 2;
        }

        int r = n - 1;
        while (r > 0 && nums[r - 1] < nums[r]) {
            r--;
        }

        // Case 1: Removing a subarray starting at index 0 (empty prefix left).
        // The remaining suffix must be strictly increasing, so it must start at or after r.
        // This means we remove nums[0...j] where j+1 >= r, so j >= r-1.
        // j can be r-1, ..., n-1. This gives n-r+1 subarrays.
        long count = n - r + 1;

        // Case 2: Removing a subarray leaving a non-empty prefix nums[0...i] where 0 <= i <= l.
        for (int i = 0; i <= l; i++) {
            int target = nums[i];
            // Binary search for the first element in nums[r...n-1] > target.
            int low = r, high = n - 1;
            int p = n; // This will be the start index of the valid suffix part.
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (nums[mid] > target) {
                    p = mid;
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            // Valid suffixes start from p, p+1, ..., n-1. And the empty suffix.
            // Total valid suffix choices: (n - p) + 1.
            count += (n - p) + 1;
        }

        return count;
    }
}
```
### Algorithm
*   **Find Boundaries:**
    1.  Find `l`, the end index of the longest strictly increasing prefix of `nums`.
    2.  Find `r`, the start index of the longest strictly increasing suffix of `nums`.
*   **Handle Sorted Case:**
    1.  If `l >= r`, the entire array is already strictly increasing. Any subarray removal will result in a strictly increasing array. The total number of non-empty subarrays is `n * (n + 1) / 2`. Return this value.
*   **Count Incremovable Subarrays:**
    1.  Initialize `count`. Start by counting removals that leave an empty prefix. This occurs when we remove `nums[0...j]`. The remaining suffix `nums[j+1...n-1]` is valid if `j+1 >= r`. This gives `n-r+1` such subarrays. So, `count = n - r + 1`.
    2.  Iterate through each valid non-empty prefix, which are `nums[0...i]` for `i` from `0` to `l`.
    3.  For each prefix, find how many valid suffixes can follow it. A suffix starting at `p` is valid if `p >= r` and `nums[p] > nums[i]`.
    4.  Since `nums[r...n-1]` is sorted, we can use **binary search** to find the first index `p >= r` where `nums[p] > nums[i]`.
    5.  The number of valid non-empty suffixes is `n - p`. Adding the case for an empty suffix, we have `(n - p) + 1` valid choices for the remaining part.
    6.  Add this number to `count`.
*   **Return `count`**.

## Optimal Two-Pointers Approach
This approach is the most optimal one and builds upon the previous method. We can optimize the process of finding valid suffix partners for each prefix. In the O(n log n) approach, we performed a binary search for each prefix. However, we can notice that as we iterate through the prefixes `nums[0...i]` for `i=0, 1, ..., l`, the value of `nums[i]` is strictly increasing. This means the starting point of the valid suffix we are looking for will also be non-decreasing.

This monotonicity allows us to use a two-pointer technique. One pointer `i` iterates through the prefix elements `nums[0...l]`, and another pointer `j` scans the suffix elements `nums[r...n-1]`. Since `j` never needs to move backward, the search for all prefixes can be done in a single combined pass, leading to a linear time solution.
**Time:** O(n). Finding `l` and `r` takes O(n). The two-pointer traversal also takes O(n) because each pointer (`i` and `j`) traverses its respective part of the array at most once. · **Space:** O(1). The solution uses a constant amount of extra space.
**Pros:** Provides the most optimal time complexity of O(n).; Highly efficient and scales well for large inputs.
**Cons:** The logic can be subtle to get right, especially with pointer initialization and loop conditions.
### Explanation
The overall strategy is the same: find `l` and `r`, then count valid prefix-suffix pairings. The optimization comes from how we count the pairings for non-empty prefixes.

We use a pointer `i` to iterate from `0` to `l`, representing the end of the prefix `nums[0...i]`. We use another pointer `j`, initialized to `r`, to find the start of a valid suffix. For each `i`, we advance `j` just enough to find the first element `nums[j]` that is greater than `nums[i]`. Since `nums[i]` increases as `i` increases, `j` will only ever move forward. The total number of steps taken by `i` and `j` combined is at most `l + (n-r)`, which is O(n).

```java
class Solution {
    public long incremovableSubarrayCount(int[] nums) {
        int n = nums.length;
        int l = 0;
        while (l + 1 < n && nums[l] < nums[l + 1]) {
            l++;
        }

        // If the whole array is strictly increasing, any subarray is incremovable.
        if (l == n - 1) {
            return (long)n * (n + 1) / 2;
        }

        int r = n - 1;
        while (r > 0 && nums[r - 1] < nums[r]) {
            r--;
        }

        // Case 1: Removing a subarray that leaves an empty prefix.
        // This means removing nums[0...j]. The remaining part is nums[j+1...n-1].
        // This must be a strictly increasing suffix, so j+1 >= r, which means j >= r-1.
        // j can be r-1, r, ..., n-1. This gives (n-1) - (r-1) + 1 = n-r+1 subarrays.
        long count = n - r + 1;

        // Case 2: Removing a subarray that leaves a non-empty prefix nums[0...i] where 0 <= i <= l.
        int j = r;
        for (int i = 0; i <= l; i++) {
            int target = nums[i];
            // Use the second pointer j to find the first element in the suffix part > target.
            // We can continue the search from j's previous position due to monotonicity.
            while (j < n && nums[j] <= target) {
                j++;
            }
            // For the prefix ending at nums[i], any suffix starting from nums[j] is valid.
            // The number of valid non-empty suffixes is n - j.
            // We also add 1 for the case of an empty suffix (removing up to the end).
            count += (n - j) + 1;
        }

        return count;
    }
}
```
### Algorithm
*   **Find Boundaries:**
    1.  Find `l`, the end index of the longest strictly increasing prefix.
    2.  Find `r`, the start index of the longest strictly increasing suffix.
*   **Handle Sorted Case:**
    1.  If `l >= r`, the array is sorted. Return `n * (n + 1) / 2`.
*   **Count using Two Pointers:**
    1.  Initialize `count = n - r + 1`. This accounts for all removals that leave an empty prefix.
    2.  Initialize a second pointer `j = r`.
    3.  Use a primary pointer `i` to iterate through the valid prefixes, from `i = 0` to `l`.
    4.  For each `i`, `nums[i]` is the last element of the current prefix. We need to find the first element in `nums[r...n-1]` that is greater than `nums[i]`.
    5.  Instead of a new search, we advance the `j` pointer from its last position: `while (j < n && nums[j] <= nums[i]) { j++; }`.
    6.  After the `while` loop, `j` is the index of the first element in the suffix part that is larger than `nums[i]`. The number of valid suffixes is `(n - j)` (non-empty) `+ 1` (empty).
    7.  Add `n - j + 1` to the `count`.
*   **Return `count`**.

# Solutions
### Java

```java
class Solution {
public
  long incremovableSubarrayCount(int[] nums) {
    int i = 0, n = nums.length;
    while (i + 1 < n && nums[i] < nums[i + 1]) {
      ++i;
    }
    if (i == n - 1) {
      return n * (n + 1L) / 2;
    }
    long ans = i + 2;
    for (int j = n - 1; j > 0; --j) {
      while (i >= 0 && nums[i] >= nums[j]) {
        --i;
      }
      ans += i + 2;
      if (nums[j - 1] >= nums[j]) {
        break;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long incremovableSubarrayCount(vector<int> &nums) {
    int i = 0, n = nums.size();
    while (i + 1 < n && nums[i] < nums[i + 1]) {
      ++i;
    }
    if (i == n - 1) {
      return n * (n + 1LL) / 2;
    }
    long long ans = i + 2;
    for (int j = n - 1; j > 0; --j) {
      while (i >= 0 && nums[i] >= nums[j]) {
        --i;
      }
      ans += i + 2;
      if (nums[j - 1] >= nums[j]) {
        break;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def incremovableSubarrayCount(self, nums: List[int]) -> int: i, n = 0, len(nums) while i + 1 < n and nums[i] < nums[i + 1]: i += 1 if i == n - 1: return n * (n + 1) // 2 ans = i + 2 j = n - 1 while j: while i >= 0 and nums[i] >= nums[j]: i -= 1 ans += i + 2 if nums[j - 1] >= nums[j]: break j -= 1 return ans

```