# Count the Number of Incremovable Subarrays I
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-the-number-of-incremovable-subarrays-i)
Canonical: https://scaleengineer.com/dsa/problems/count-the-number-of-incremovable-subarrays-i
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
---
## 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 <= 50`
* `1 <= nums[i] <= 50`

# Approaches
## Brute-Force Simulation
The most straightforward approach is to simulate the process described in the problem. We can generate every possible subarray, conceptually remove it, and then check if the remaining elements form a strictly increasing sequence. If they do, we count that subarray as an "incremovable" one.
**Time:** O(n³)

There are O(n²) possible subarrays. For each subarray, we construct a new list of up to `n` elements, which takes O(n) time. Checking if this list is sorted also takes O(n) time. Therefore, the total time complexity is O(n² * n) = O(n³). · **Space:** O(n)

The space complexity is O(n) because, in the worst case, we create a temporary list of size `n-1` to check if the remaining elements are sorted.
**Pros:** Simple to understand and implement.; Directly follows the problem statement.
**Cons:** Inefficient due to cubic time complexity.; Creates a new list for every subarray check, which consumes extra space and time.
### Explanation
This method involves iterating through all possible start and end indices, `i` and `j`, to define a subarray `nums[i..j]`. For each of these subarrays, we construct a new array that contains all elements of `nums` except for those in the range `[i, j]`. Then, we check if this newly formed array is strictly increasing. A helper function can be used for this check. If the check passes, we increment a counter. The total count after checking all subarrays is the answer.

```java
class Solution {
    public int incremovableSubarrayCount(int[] nums) {
        int n = nums.length;
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (isIncremovable(nums, i, j)) {
                    count++;
                }
            }
        }
        return count;
    }

    private boolean isIncremovable(int[] nums, int start, int end) {
        java.util.List<Integer> remaining = new java.util.ArrayList<>();
        for (int i = 0; i < start; i++) {
            remaining.add(nums[i]);
        }
        for (int i = end + 1; i < nums.length; i++) {
            remaining.add(nums[i]);
        }

        if (remaining.size() <= 1) {
            return true;
        }

        for (int i = 0; i < remaining.size() - 1; i++) {
            if (remaining.get(i) >= remaining.get(i + 1)) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
1. Initialize a counter `count` to 0.
2. Get the length of the array, `n`.
3. Use nested loops to iterate through all possible subarrays `nums[i..j]`.
   - The outer loop for the start index `i` runs from `0` to `n-1`.
   - The inner loop for the end index `j` runs from `i` to `n-1`.
4. For each subarray `nums[i..j]`, simulate its removal by creating a temporary array or list.
   - Add elements from the prefix `nums[0..i-1]` to the temporary list.
   - Add elements from the suffix `nums[j+1..n-1]` to the temporary list.
5. Write a helper function to check if the temporary list is strictly increasing.
   - An empty or single-element list is considered strictly increasing.
   - Iterate through the list and check if `temp[k] >= temp[k+1]` for any `k`.
6. If the temporary list is strictly increasing, increment the `count`.
7. After checking all subarrays, return the final `count`.

## Identifying Valid Prefix/Suffix Ranges
We can optimize the brute-force approach by observing the properties of the remaining array. After removing a subarray `nums[i..j]`, the remaining parts are a prefix `nums[0..i-1]` and a suffix `nums[j+1..n-1]`. For the combined sequence to be strictly increasing, the prefix itself must be strictly increasing, the suffix itself must be strictly increasing, and the last element of the prefix must be smaller than the first element of the suffix. This observation allows us to limit the search space for the start and end indices of the removable subarray.
**Time:** O(n²)

Finding the prefix and suffix boundaries `l` and `r` takes O(n) time. The nested loops for `i` and `j` run up to `n` times each in the worst case (e.g., for an array like `[1, 2, ..., k, n, n-1, ..., k+1]`), leading to a time complexity of O(n²). · **Space:** O(1)

This approach only uses a few variables to store indices and the count, resulting in constant extra space.
**Pros:** Significantly more efficient than the O(n³) brute-force approach.; Avoids the creation of temporary arrays, reducing space complexity to O(1).
**Cons:** Still has a quadratic time complexity, which might be slow for larger constraints, although it passes for n <= 50.
### Explanation
First, we find the longest strictly increasing prefix and suffix. Let the prefix end at index `l` and the suffix start at index `r`. Any valid removal `nums[i..j]` must ensure that the remaining prefix `nums[0..i-1]` is contained within `nums[0..l]` and the remaining suffix `nums[j+1..n-1]` is contained within `nums[r..n-1]`. This means `i` can be at most `l+1` and `j` must be at least `r-1`.

We can then iterate through the limited ranges for `i` (from `0` to `l+1`) and `j` (from `r-1` to `n-1`). For each pair `(i, j)` where `i <= j`, we check if `nums[i-1] < nums[j+1]`. Special care is taken for cases where the prefix or suffix is empty (e.g., when `i=0` or `j=n-1`).

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

        if (l == n - 1) { // Array is already sorted
            return n * (n + 1) / 2;
        }

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

        int count = 0;
        // Iterate through valid prefixes (ending at i-1)
        for (int i = 0; i <= l + 1; i++) {
            // Iterate through valid suffixes (starting at j+1)
            for (int j = r - 1; j < n; j++) {
                if (i <= j) {
                    long lastPrefix = (i > 0) ? nums[i - 1] : Long.MIN_VALUE;
                    long firstSuffix = (j < n - 1) ? nums[j + 1] : Long.MAX_VALUE;
                    if (lastPrefix < firstSuffix) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}
```
### Algorithm
1. Identify the longest strictly increasing prefix of the array. Let its end index be `l`.
2. Identify the longest strictly increasing suffix of the array. Let its start index be `r`.
3. If `l >= r`, the entire array is strictly increasing. Any subarray removal will result in a strictly increasing sequence. The total number of subarrays is `n * (n+1) / 2`, so we can return this value.
4. Otherwise, initialize a counter `count` to 0.
5. An incremovable subarray `nums[i..j]` must leave a prefix `nums[0..i-1]` and a suffix `nums[j+1..n-1]` that are both strictly increasing and correctly ordered with respect to each other.
6. This implies that the start index `i` of the removed subarray can be at most `l+1`, and the end index `j` must be at least `r-1`.
7. Iterate through all possible start indices `i` from `0` to `l+1`.
8. For each `i`, iterate through all possible end indices `j` from `r-1` to `n-1`.
9. If `i <= j`, check the connection condition: the last element of the prefix (`nums[i-1]`) must be less than the first element of the suffix (`nums[j+1]`). Handle edge cases where the prefix or suffix is empty.
10. If the condition holds, increment the `count`.
11. Return the final `count`.

## Two-Pointer Optimal Approach
This optimal approach builds upon the previous one by further optimizing the counting process. After identifying the strictly increasing prefix and suffix, we can count the valid combinations of prefixes and suffixes in linear time. We can iterate through all possible valid prefixes and, for each one, efficiently count the number of valid suffixes that can follow it. By using a second pointer that doesn't reset, we can achieve an overall linear time complexity.
**Time:** O(n)

Finding `l` and `r` takes O(n). The main loop iterates `i` from `0` to `l+1`. The inner pointer `j` only moves forward across the array. Since both `i` and `j` traverse parts of the array at most once, the total time complexity is O(n). · **Space:** O(1)

This approach uses only a constant amount of extra space for pointers and variables.
**Pros:** Most efficient solution with linear time complexity.; Optimal space complexity of O(1).
**Cons:** The logic is more complex to reason about compared to the brute-force methods.
### Explanation
We first find the boundaries `l` and `r` as before. The core idea is to count pairs `(prefix, suffix)` that work. We can fix the prefix and count the valid suffixes.

We iterate through possible prefixes by considering their end points. A prefix can be `nums[0...i-1]` where `i` ranges from `0` to `l+1`. For each `i`, we need to find the number of suffixes `nums[k...n-1]` such that:
1. The suffix is strictly increasing (`k >= r`).
2. The connection is valid: `nums[i-1] < nums[k]` (if prefix and suffix are non-empty).
3. The removed part is non-empty: `k > i`.

We can iterate `i` from `0` to `l+1`. For each `i`, we determine the value of the last element of the prefix, `last_val`. Then, we need to find how many `k`'s satisfy the conditions. Since `nums[r...n-1]` is sorted, as `i` (and thus `last_val`) increases, the minimum valid `k` will also only increase or stay the same. This monotonicity allows us to use a two-pointer technique. One pointer `i` scans through prefixes, and another pointer `k` scans through potential suffix start points, without ever moving backward.

For each `i`, we advance `k` from its previous position to find the first index where `nums[k] > last_val`. The number of valid suffixes is then all suffixes starting from `max(k, i+1)` to `n`, which can be calculated directly.

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

        if (l == n - 1) { // Array is already sorted
            return n * (n + 1) / 2;
        }

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

        long count = 0;
        // Case 1: Remove a suffix of the array, leaving a valid prefix.
        // The prefixes nums[0...i-1] are valid for i from 0 to l+1.
        // Removing nums[i...n-1] leaves a valid prefix.
        // This gives l+2 subarrays (for i=0..l+1).
        count = l + 2;

        // Case 2: The remaining prefix is nums[0...i-1] and suffix is nums[k...n-1].
        // We already counted cases where the suffix is empty (k=n).
        // Now we count for non-empty suffixes.
        for (int i = 0; i <= l; i++) {
            int lastPrefixVal = nums[i];
            // We need to find k such that nums[k] > lastPrefixVal and k >= r.
            // We can use binary search or two pointers. Here we use binary search for clarity.
            int low = r, high = n - 1, p = n;
            while(low <= high) {
                int mid = low + (high - low) / 2;
                if (nums[mid] > lastPrefixVal) {
                    p = mid;
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            // All suffixes starting from p to n-1 are valid.
            count += (n - p);
        }

        return count;
    }
}
// A slightly different but equivalent O(n) two-pointer implementation:
class SolutionTwoPointer {
    public int incremovableSubarrayCount(int[] nums) {
        int n = nums.length;
        int l = 0;
        while (l < n - 1 && nums[l] < nums[l + 1]) {
            l++;
        }
        if (l == n - 1) return n * (n + 1) / 2;

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

        // Count subarrays that are suffixes of nums[0..r-1]
        // This means removing nums[0..j] where j < r-1.
        // The remaining part nums[j+1..n-1] must be increasing, so j+1 >= r.
        // This gives n-r+1 subarrays (for j=r-1..n-1).
        long count = n - r + 1;

        // Now, fix prefix nums[0..i] for i in [0, l] and find valid suffixes.
        int k = r;
        for (int i = 0; i <= l; i++) {
            while (k < n && nums[k] <= nums[i]) {
                k++;
            }
            // For prefix nums[0..i], suffixes starting from k to n-1 are valid.
            // This gives n-k valid non-empty suffixes.
            // We also need to count the empty suffix case.
            count += (n - k + 1);
        }
        // The above double counts cases where both prefix and suffix are kept.
        // A simpler O(n) logic is as follows:
        count = 0;
        int j = r;
        for (int i = 0; i <= l + 1; i++) {
            long lastVal = (i > 0) ? nums[i - 1] : -1;
            while (j < n && nums[j] <= lastVal) {
                j++;
            }
            // For prefix nums[0..i-1], suffixes starting from j to n-1 are valid.
            // This gives n-j valid non-empty suffixes.
            // Plus one for the empty suffix.
            count += (n - j + 1);
        }
        return (int)count;
    }
}
```
### Algorithm
1. Find the end `l` of the longest strictly increasing prefix and the start `r` of the longest strictly increasing suffix.
2. If `l >= r`, the array is sorted. Return `n * (n+1) / 2`.
3. The problem is now to count pairs of a valid prefix `nums[0..i-1]` and a valid suffix `nums[k..n-1]` that can form a strictly increasing sequence.
4. A prefix `nums[0..i-1]` is valid if `i-1 <= l`. This means we can choose prefixes of length `i` from `0` to `l+1`.
5. A suffix `nums[k..n-1]` is valid if `k >= r`.
6. We iterate through each possible prefix (by iterating `i` from `0` to `l+1`). For each prefix, we count how many valid suffixes can follow it.
7. For a prefix ending with `nums[i-1]`, a suffix starting with `nums[k]` can follow if `nums[i-1] < nums[k]`. Also, the removed subarray `nums[i..k-1]` must be non-empty, so `k > i`.
8. We can use a two-pointer approach. One pointer `i` iterates through the valid prefix lengths `0` to `l+1`. Another pointer `k` starts at `r` and finds the first valid suffix for the current prefix.
9. As `i` increases, `nums[i-1]` increases. Thus, the required `nums[k]` also increases, meaning the pointer `k` will only move forward. This avoids a nested loop or repeated searches.
10. For each `i`, we find the smallest `k >= r` such that `nums[k] > nums[i-1]`. All suffixes starting from this `k` up to `n-1` are valid, plus the empty suffix. We add this count to our total.

# Solutions
### Java

```java
class Solution { public int 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 + 1 ) / 2 ; } int 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: int 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 + 1 ) / 2 ; } int 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
```