Count the Number of Incremovable Subarrays I

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 <= 50
• 1 <= nums[i] <= 50

Solution

Method 1 – Brute Force with Two Pointers

Intuition

A subarray is incremovable if, after removing it, the remaining array is strictly increasing. Since the array is small (n ≤ 50), we can check all possible subarrays by removing them and verifying if the result is strictly increasing.

Approach

1. For every possible subarray nums[l:r] (0 ≤ l ≤ r < n):
   • Remove nums[l:r+1] from nums.
   • Check if the remaining array is strictly increasing.
   • If yes, count this subarray as incremovable.
2. Return the total count.

Code

C++

class Solution {
public:
    int incremovableSubarrayCount(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        for (int l = 0; l < n; ++l) {
            for (int r = l; r < n; ++r) {
                vector<int> arr;
                for (int i = 0; i < l; ++i) arr.push_back(nums[i]);
                for (int i = r+1; i < n; ++i) arr.push_back(nums[i]);
                bool ok = true;
                for (int i = 1; i < arr.size(); ++i) {
                    if (arr[i] <= arr[i-1]) ok = false;
                }
                if (ok) ans++;
            }
        }
        return ans;
    }
};

Java

class Solution {
    public int incremovableSubarrayCount(int[] nums) {
        int n = nums.length, ans = 0;
        for (int l = 0; l < n; ++l) {
            for (int r = l; r < n; ++r) {
                List<Integer> arr = new ArrayList<>();
                for (int i = 0; i < l; ++i) arr.add(nums[i]);
                for (int i = r+1; i < n; ++i) arr.add(nums[i]);
                boolean ok = true;
                for (int i = 1; i < arr.size(); ++i) {
                    if (arr.get(i) <= arr.get(i-1)) ok = false;
                }
                if (ok) ans++;
            }
        }
        return ans;
    }
}

Python

class Solution:
    def incremovableSubarrayCount(self, nums: list[int]) -> int:
        n = len(nums)
        ans = 0
        for l in range(n):
            for r in range(l, n):
                arr = nums[:l] + nums[r+1:]
                if all(arr[i] > arr[i-1] for i in range(1, len(arr))):
                    ans += 1
        return ans

Complexity

• ⏰ Time complexity: O(n^3), where n is the length of nums, since we check all subarrays and verify increasing order.
• 🧺 Space complexity: O(n), for the temporary array.