Watch 4 video solutions for Count the Number of Incremovable Subarrays I, a easy level problem involving Array, Two Pointers, Binary Search. This walkthrough by Developer Docs has 2,214 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 <= 501 <= nums[i] <= 50Problem Overview: You are given an integer array nums. A subarray is called incremovable if removing that subarray makes the remaining elements strictly increasing. The task is to count how many such subarrays exist.
Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)
The most direct approach is to enumerate every possible subarray [l, r] and simulate removing it. After removal, iterate through the remaining elements and verify whether they form a strictly increasing sequence. This requires three steps: choose l, choose r, and check the resulting array. The validation step scans the remaining elements to confirm nums[i] < nums[i+1]. Because there are O(n^2) subarrays and each validation can take O(n), the total complexity becomes O(n^3). This method is useful for understanding the definition of incremovable subarrays and verifying correctness on small inputs.
Approach 2: Optimized Sliding Window with Two Pointers (O(n) time, O(1) space)
The optimized solution relies on the observation that the remaining array must consist of a strictly increasing prefix and suffix that connect correctly after removal. First, find the longest strictly increasing prefix. If the entire array is already increasing, every subarray removal works and the answer becomes n * (n + 1) / 2. Otherwise, use a two pointers or sliding window technique: move a right pointer from the end while maintaining a strictly increasing suffix. For each valid suffix start, shift the left pointer within the prefix until the boundary condition nums[left] < nums[right] holds. Each valid pair represents a removable middle segment. This effectively counts all valid removals while scanning the array once. The method uses ideas from array traversal and monotonic structure checks, reducing the complexity to linear time.
Some implementations also treat the prefix boundary with binary search to find the largest valid connection point, though the two‑pointer sweep already achieves optimal performance.
Recommended for interviews: Interviewers expect the linear-time two‑pointer approach. The brute force method demonstrates understanding of the definition, but recognizing the increasing prefix and suffix structure shows stronger algorithmic intuition and leads to the O(n) solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^3) | O(1) | Useful for understanding the definition and verifying logic on very small arrays |
| Sliding Window / Two Pointers | O(n) | O(1) | Best general solution for interviews and production constraints |