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.
The brute-force approach involves iterating over all possible subarrays of the input array and, for each subarray, checking if removing it makes the array strictly increasing. For an array of length n, there are n(n+1)/2 possible subarrays. We'll iterate over each of these subarrays, remove it from the array, and check if the remaining array is strictly increasing. This approach is more understandable but can be less efficient for larger arrays.
This code checks each possible subarray of the given array nums. If removing the subarray results in a strictly increasing sequence, it counts that subarray as incremovable. The function is_strictly_increasing verifies whether an array is strictly increasing.
Time Complexity: O(n^3), where n is the length of the input array, due to the nested loops and increasing check.
Space Complexity: O(n), which is needed for constructing subarrays.
Instead of checking all potential subarrays, an optimized sliding window approach could significantly reduce the number of operations. The idea is to identify subarrays around breaking points in the array where it's not strictly increasing and expand around those to compute only potential subarrays that result in a stricter list after removal.
This JavaScript function calculates the number of incremovable subarrays more efficiently using a single scan through the list. It leverages the concept of running count adjustments each time a slide window satisfies strict increasing conditions.
JavaScript
Java
Time Complexity: O(n^2) in the worst case due to the nested nature but significantly reduced operations per iteration.
Space Complexity: O(1), only uses a few variables beyond the input array.
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 |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3), where n is the length of the input array, due to the nested loops and increasing check. |
| Optimized Sliding Window Approach | Time Complexity: O(n^2) in the worst case due to the nested nature but significantly reduced operations per iteration. |
| Two Pointers | — |
| 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 |
Leetcode | 2970. Count the Number of Incremovable Subarrays I | Easy | Java Solution • Developer Docs • 2,214 views views
Watch 3 more video solutions →Practice Count the Number of Incremovable Subarrays I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor