Count the Number of Incremovable Subarrays II

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 ofincremovable 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.

Examples

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 <= 10^5
• 1 <= nums[i] <= 10^9

Solution

Method 1 – Two Pointers and Binary Search

Intuition

A subarray is incremovable if, after removing it, the remaining array is strictly increasing. For large arrays, we can precompute the longest strictly increasing prefix and suffix, and for each possible subarray, check if removing it results in a strictly increasing array using binary search and two pointers.

Approach

1. Compute the longest strictly increasing prefix (pre) and suffix (suf).
2. For each possible left endpoint l, find the smallest right endpoint r such that removing nums[l:r] leaves a strictly increasing array.
3. Use binary search to efficiently find valid subarrays.
4. Count all such subarrays.
5. Return the total count.

Code

Java

class Solution {
    public int incremovableSubarrayCount(int[] nums) {
        int n = nums.length, ans = 0;
        int[] pre = new int[n+1];
        pre[0] = 1;
        for (int i = 1; i < n; ++i) pre[i] = pre[i-1] & (nums[i] > nums[i-1] ? 1 : 0);
        int[] suf = new int[n+1];
        suf[n] = 1;
        for (int i = n-1; i > 0; --i) suf[i] = suf[i+1] & (nums[i] < nums[i+1] ? 1 : 0);
        for (int l = 0; l < n; ++l) {
            for (int r = l; r < n; ++r) {
                boolean ok = true;
                if (l > 0 && r < n-1 && nums[l-1] >= nums[r+1]) ok = false;
                if (l > 0 && pre[l-1] == 0) ok = false;
                if (r < n-1 && suf[r+1] == 0) ok = false;
                if (ok) ans++;
            }
        }
        return ans;
    }
}

Python

class Solution:
    def incremovableSubarrayCount(self, nums: list[int]) -> int:
        n = len(nums)
        pre = [True] * (n+1)
        for i in range(1, n):
            pre[i] = pre[i-1] and nums[i] > nums[i-1]
        suf = [True] * (n+1)
        for i in range(n-2, -1, -1):
            suf[i] = suf[i+1] and nums[i] < nums[i+1]
        ans = 0
        for l in range(n):
            for r in range(l, n):
                ok = True
                if l > 0 and r < n-1 and nums[l-1] >= nums[r+1]:
                    ok = False
                if l > 0 and not pre[l-1]:
                    ok = False
                if r < n-1 and not suf[r+1]:
                    ok = False
                if ok:
                    ans += 1
        return ans

Complexity

• ⏰ Time complexity: O(n^2), where n is the length of nums, since we check all subarrays with precomputed prefix/suffix.
• 🧺 Space complexity: O(n), for prefix and suffix arrays.