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 <= 501 <= nums[i] <= 50In #2970 Count the Number of Incremovable Subarrays I, the goal is to count how many subarrays can be removed so that the remaining elements form a strictly increasing array. A key observation is that the remaining array is composed of a prefix and a suffix after removing a middle segment.
Start by identifying the longest strictly increasing prefix and strictly increasing suffix. If the entire array is already strictly increasing, then every possible subarray removal is valid. Otherwise, we can iterate through valid prefix endpoints and attempt to connect them with valid suffix starting points while maintaining the increasing property.
A two pointers technique works well here. One pointer scans the prefix while another tracks the earliest valid suffix position where nums[left] < nums[right]. By carefully counting valid combinations, we can enumerate all removable subarrays efficiently without checking every possibility.
This approach reduces unnecessary checks and achieves O(n) time complexity with O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Prefix-Suffix Scan with Two Pointers | O(n) | O(1) |
Striver
Use these hints if you're stuck. Try solving on your own first.
Use two loops to check all the subarrays.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, similar array and two-pointer pattern problems are common in coding interviews. They test a candidate's ability to reason about monotonic properties, array segmentation, and efficient enumeration.
Two pointers help track valid prefix and suffix boundaries while ensuring the remaining array stays strictly increasing. This avoids checking every subarray individually and significantly improves efficiency.
The problem mainly relies on array traversal, so no advanced data structure is required. Simple index pointers over the array are sufficient to maintain the increasing order constraints.
The optimal approach uses a prefix and suffix analysis combined with a two-pointer technique. By identifying strictly increasing segments from both ends and counting valid connections, we can compute the number of removable subarrays efficiently in linear time.