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 <= 1051 <= nums[i] <= 109Problem Overview: You are given an integer array and must count how many subarrays can be removed so that the remaining elements form a strictly increasing sequence. After removing a contiguous segment [l, r], the prefix before l and the suffix after r must still connect into a valid increasing array.
Approach 1: Sliding Window with Increasing Prefix/Suffix (O(n) time, O(1) space)
Start by finding the longest strictly increasing prefix from the left. If the entire array is already increasing, every subarray removal works. Otherwise, use a two pointer strategy: keep one pointer in the prefix and another scanning possible suffix starts from the right. The key observation is that both the prefix and suffix must individually remain strictly increasing, and the last value of the prefix must be smaller than the first value of the suffix. Move the right pointer leftward while maintaining a valid increasing suffix, then adjust the left pointer to maintain the cross-boundary condition. This behaves like a sliding window over valid split points and counts valid removals efficiently.
This approach works because once the suffix is strictly increasing, expanding the prefix pointer only reduces valid suffix positions. The two pointers move monotonically, so the entire scan runs in linear time. It’s a classic application of two pointers on an array with strict ordering constraints.
Approach 2: Efficient Linear Scan with Previous and Next Arrays (O(n) time, O(n) space)
Another strategy precomputes structural information about the array. Build helper arrays that track whether prefixes and suffixes remain strictly increasing. For each index, determine whether it can serve as a valid boundary after removing a middle subarray. Using these arrays, you can quickly verify if the prefix ending at i and the suffix starting at j are valid and satisfy nums[i] < nums[j].
Once prefix and suffix validity are known, iterate through candidate prefix endpoints and locate the earliest compatible suffix start. A binary search or linear pointer advancement finds the first suffix element greater than the prefix boundary value. Every suffix position beyond that point forms a valid removable segment.
This method is easier to reason about when you want explicit prefix/suffix state rather than maintaining window invariants. The tradeoff is O(n) additional memory for the helper arrays.
Recommended for interviews: The sliding window two-pointer solution is the one most interviewers expect. It achieves O(n) time with constant space and demonstrates strong reasoning about monotonic properties in arrays. Showing the prefix/suffix insight first helps explain correctness, but implementing the two-pointer scan proves you can translate that reasoning into an optimal solution.
This approach uses the sliding window technique. By considering each subarray and checking if removing it results in a strictly increasing array, we can count how many such valid subarrays exist. The key here is to move a window across the array and check if removing elements from the current window causes the array to be strictly increasing.
The code iterates through all possible subarrays and checks if the remaining elements form a strictly increasing sequence. It uses a nested loop to achieve this and increments the counter if the condition for a strictly increasing array holds.
Time Complexity: O(n^3) - The approach involves iterating over every possible subarray and checking its elements, resulting in a cubic complexity.
Space Complexity: O(1) - The algorithm only uses a fixed amount of additional space.
This approach involves using two auxiliary arrays to keep track of the longest increasing subarray up to each point from the start and end. We can leverage these arrays to efficiently determine when removing a segment results in a strictly increasing list.
This C program uses two arrays, left and right, to store the longest increasing sequences from the start and end of the array, respectively. This allows concise calculations for potential removals and makes for a more efficient solution.
Time Complexity: O(n) - The approach involves linear scans and adds auxiliary space but avoids nested operations.
Space Complexity: O(n) - Two additional arrays of size n are required.
According to the problem description, after removing a subarray, the remaining elements are strictly increasing. Therefore, there are several situations:
nums (which can be empty);nums;nums.The second and third situations can be combined into one, that is, the remaining elements include the suffix of the array nums. So there are two situations in total:
nums (which can be empty);nums.First, consider the first situation, that is, the remaining elements only include the prefix of the array nums. We can use a pointer i to point to the last element of the longest increasing prefix of the array nums, that is, nums[0] \lt nums[1] \lt cdots \lt nums[i], then the number of remaining elements is n - i - 1, where n is the length of the array nums. Therefore, for this situation, to make the remaining elements strictly increasing, we can choose to remove the following subarrays:
nums[i+1,...,n-1];nums[i,...,n-1];nums[i-1,...,n-1];nums[i-2,...,n-1];cdots;nums[0,...,n-1].There are i + 2 situations in total, so for this situation, the number of removed increasing subarrays is i + 2.
Next, consider the second situation, that is, the remaining elements include the suffix of the array nums. We can use a pointer j to point to the first element of the increasing suffix of the array nums. We enumerate j as the first element of the increasing suffix in the range [n - 1,...,1]. Each time, we need to move the pointer i to make nums[i] \lt nums[j], then the number of removed increasing subarrays increases by i + 2. When nums[j - 1] \ge nums[j], we stop enumerating because the suffix is not strictly increasing at this time.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sliding Window | Time Complexity: O(n^3) - The approach involves iterating over every possible subarray and checking its elements, resulting in a cubic complexity. |
| Efficient Linear Scan with Previous and Next Arrays | Time Complexity: O(n) - The approach involves linear scans and adds auxiliary space but avoids nested operations. |
| Two Pointers | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window with Two Pointers | O(n) | O(1) | Best general solution. Optimal for interviews and large inputs. |
| Prefix/Suffix Arrays + Linear Scan | O(n) | O(n) | Useful when explicit prefix and suffix validity checks simplify reasoning. |
| Prefix with Binary Search on Suffix | O(n log n) | O(1) | Good when suffix positions are pre-sorted and binary search is easier to implement. |
Count the Number of Incremovable Subarrays II | Leetcode Biweekly 120 • codingMohan • 3,007 views views
Watch 3 more video solutions →Practice Count the Number of Incremovable Subarrays II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor