Watch 4 video solutions for Count the Number of Incremovable Subarrays II, a hard level problem involving Array, Two Pointers, Binary Search. This walkthrough by codingMohan has 3,007 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |