Count the Number of Incremovable Subarrays II solution and explanation
IBM
2 more videos on this problem
Count the Number of Incremovable Subarrays II | Leetcode Biweekly 120codingMohan · 33:11 · 3K views
2972. Count the Number of Incremovable Subarrays II (Leetcode Medium)Programming Live with Larry · 23:04 · 899 views
2972 || Count the Number of Incremovable Subarrays II || Leetcode Hard || Bi-Weekly Contest 120Harsit Sinha · 20:48 · 881 views
The problem
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] <= 109
Approach overview
Problem 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 1: Sliding Window
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.
def count_incremovable_subarrays(nums):
count = 0
n = len(nums)
for i in range(n):
for j in range(i, n):
is_increasing = True
for k in range(n - 1):
if (k < i or k > j) and nums[k] >= nums[k + 1]:
is_increasing = False
break
if is_increasing:
count += 1
return count
nums = [1, 2, 3, 4]
print(count_incremovable_subarrays(nums))public class Main {
public static int countIncremovableSubarrays(int[] nums) {
int count = 0;
int n = nums.length;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
boolean isIncreasing = true;
for (int k = 0; k < n - 1; k++) {
if ((k < i || k > j) && nums[k] >= nums[k + 1]) {
isIncreasing = false;
break;
}
}
if (isIncreasing) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4};
System.out.println(countIncremovableSubarrays(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
int countIncremovableSubarrays(vector<int>& nums) {
int count = 0;
int n = nums.size();
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
bool isIncreasing = true;
for (int k = 0; k < n - 1; k++) {
if ((k < i || k > j) && nums[k] >= nums[k + 1]) {
isIncreasing = false;
break;
}
}
if (isIncreasing) {
count++;
}
}
}
return count;
}
int main() {
vector<int> nums = {1, 2, 3, 4};
cout << countIncremovableSubarrays(nums) << endl;
return 0;
}function countIncremovableSubarrays(nums) {
let count = 0;
let n = nums.length;
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
let isIncreasing = true;
for (let k = 0; k < n - 1; k++) {
if ((k < i || k > j) && nums[k] >= nums[k + 1]) {
isIncreasing = false;
break;
}
}
if (isIncreasing) {
count++;
}
}
}
return count;
}
let nums = [1, 2, 3, 4];
console.log(countIncremovableSubarrays(nums));#include <stdio.h>
int countIncremovableSubarrays(int* nums, int numsSize) {
int count = 0;
for (int i = 0; i < numsSize; i++) {
for (int j = i; j < numsSize; j++) {
int k;
int isIncreasing = 1;
for (k = 0; k < numsSize - 1; k++) {
if (k < i || k > j) {
if (k < numsSize - 1 && nums[k] >= nums[k + 1]) {
isIncreasing = 0;
break;
}
}
}
if (isIncreasing) {
count++;
}
}
}
return count;
}
int main() {
int nums[] = {1, 2, 3, 4};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", countIncremovableSubarrays(nums, numsSize));
return 0;
}using System;
class Program {
public static int CountIncremovableSubarrays(int[] nums) {
int count = 0;
int n = nums.Length;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
bool isIncreasing = true;
for (int k = 0; k < n - 1; k++) {
if ((k < i || k > j) && nums[k] >= nums[k + 1]) {
isIncreasing = false;
break;
}
}
if (isIncreasing) {
count++;
}
}
}
return count;
}
static void Main() {
int[] nums = { 1, 2, 3, 4 };
Console.WriteLine(CountIncremovableSubarrays(nums));
}
}The Python solution iterates over all possible subarrays and checks if the remainder of the list after removing the subarray is strictly increasing. It uses a simple loop setup and condition checking to determine this.
Time Complexity: O(n^3)
Space Complexity: O(1)
Approach 2: Efficient Linear Scan with Previous and Next Arrays
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.
def count_incremovable_subarrays(nums):
n = len(nums)
left = [1] * n
right = [1] * n
for i in range(1, n):
left[i] = left[i - 1] + 1 if nums[i] > nums[i - 1] else 1
for i in range(n - 2, -1, -1):
right[i] = right[i + 1] + 1 if nums[i] < nums[i + 1] else 1
count = 0
for i in range(n):
li = left[i - 1] if i > 0 else 0
ri = right[i + 1] if i + 1 < n else 0
if li + ri == n - 1:
count += 1
return count
nums = [1, 2, 3, 4]
print(count_incremovable_subarrays(nums))public class Main {
public static int countIncremovableSubarrays(int[] nums) {
int n = nums.length;
int[] left = new int[n];
int[] right = new int[n];
for (int i = 1; i < n; i++)
left[i] = nums[i] > nums[i - 1] ? left[i - 1] + 1 : 1;
for (int i = n - 2; i >= 0; i--)
right[i] = nums[i] < nums[i + 1] ? right[i + 1] + 1 : 1;
int count = 0;
for (int i = 0; i < n; i++) {
int li = i > 0 ? left[i - 1] : 0;
int ri = i + 1 < n ? right[i + 1] : 0;
if (li + ri == n - 1) count++;
}
return count;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4};
System.out.println(countIncremovableSubarrays(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
int countIncremovableSubarrays(vector<int>& nums) {
int n = nums.size();
vector<int> left(n, 1), right(n, 1);
for (int i = 1; i < n; i++)
left[i] = nums[i] > nums[i - 1] ? left[i - 1] + 1 : 1;
for (int i = n - 2; i >= 0; i--)
right[i] = nums[i] < nums[i + 1] ? right[i + 1] + 1 : 1;
int count = 0;
for (int i = 0; i < n; i++) {
int li = i > 0 ? left[i - 1] : 0;
int ri = i + 1 < n ? right[i + 1] : 0;
if (li + ri == n - 1) count++;
}
return count;
}
int main() {
vector<int> nums = {1, 2, 3, 4};
cout << countIncremovableSubarrays(nums) << endl;
return 0;
}function countIncremovableSubarrays(nums) {
const n = nums.length;
const left = new Array(n).fill(1);
const right = new Array(n).fill(1);
for (let i = 1; i < n; i++) {
left[i] = nums[i] > nums[i - 1] ? left[i - 1] + 1 : 1;
}
for (let i = n - 2; i >= 0; i--) {
right[i] = nums[i] < nums[i + 1] ? right[i + 1] + 1 : 1;
}
let count = 0;
for (let i = 0; i < n; i++) {
const li = i > 0 ? left[i - 1] : 0;
const ri = i < n - 1 ? right[i + 1] : 0;
if (li + ri === n - 1) count++;
}
return count;
}
const nums = [1, 2, 3, 4];
console.log(countIncremovableSubarrays(nums));#include <stdio.h>
#include <stdlib.h>
int countIncremovableSubarrays(int* nums, int numsSize) {
int* left = (int*)malloc(numsSize * sizeof(int));
int* right = (int*)malloc(numsSize * sizeof(int));
int count = 0;
left[0] = 1;
for (int i = 1; i < numsSize; i++)
left[i] = nums[i] > nums[i-1] ? left[i-1] + 1 : 1;
right[numsSize-1] = 1;
for (int i = numsSize - 2; i >= 0; i--)
right[i] = nums[i] < nums[i+1] ? right[i+1] + 1 : 1;
for (int i = 0; i < numsSize; i++) {
int li = i > 0 ? left[i-1] : 0;
int ri = i + 1 < numsSize ? right[i+1] : 0;
if (li + ri == numsSize - 1) count++;
}
free(left);
free(right);
return count;
}
int main() {
int nums[] = {1, 2, 3, 4};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", countIncremovableSubarrays(nums, numsSize));
return 0;
}using System;
class Program {
public static int CountIncremovableSubarrays(int[] nums) {
int n = nums.Length;
int[] left = new int[n];
int[] right = new int[n];
for (int i = 1; i < n; i++)
left[i] = nums[i] > nums[i - 1] ? left[i - 1] + 1 : 1;
for (int i = n - 2; i >= 0; i--)
right[i] = nums[i] < nums[i + 1] ? right[i + 1] + 1 : 1;
int count = 0;
for (int i = 0; i < n; i++) {
int li = i > 0 ? left[i - 1] : 0;
int ri = i + 1 < n ? right[i + 1] : 0;
if (li + ri == n - 1) count++;
}
return count;
}
static void Main() {
int[] nums = { 1, 2, 3, 4 };
Console.WriteLine(CountIncremovableSubarrays(nums));
}
}This Python implementation efficiently determines valid subarray removals by using two arrays that store the lengths of increasing sequences from either end of the list. The solution is more computationally effective than a purely iterative method.
Time Complexity: O(n)
Space Complexity: O(n)
Approach 3: Two Pointers
According to the problem description, after removing a subarray, the remaining elements are strictly increasing. Therefore, there are several situations:
- The remaining elements only include the prefix of the array
nums(which can be empty); - The remaining elements only include the suffix of the array
nums; - The remaining elements include both the prefix and the suffix of the array
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:
- The remaining elements only include the prefix of the array
nums(which can be empty); - The remaining elements include the suffix of the array
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).
function incremovableSubarrayCount(nums: number[]): number {
const n = nums.length;
let i = 0;
while (i + 1 < n && nums[i] < nums[i + 1]) {
i++;
}
if (i === n - 1) {
return (n * (n + 1)) / 2;
}
let ans = i + 2;
for (let j = n - 1; j; --j) {
while (i >= 0 && nums[i] >= nums[j]) {
--i;
}
ans += i + 2;
if (nums[j - 1] >= nums[j]) {
break;
}
}
return ans;
}func incremovableSubarrayCount(nums []int) int64 {
i, n := 0, len(nums)
for i+1 < n && nums[i] < nums[i+1] {
i++
}
if i == n-1 {
return int64(n * (n + 1) / 2)
}
ans := int64(i + 2)
for j := n - 1; j > 0; j-- {
for i >= 0 && nums[i] >= nums[j] {
i--
}
ans += int64(i + 2)
if nums[j-1] >= nums[j] {
break
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window | Time Complexity: O(n^3) |
| Efficient Linear Scan with Previous and Next Arrays | Time Complexity: O(n) |
| Two Pointers | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Count the Number of Incremovable Subarrays II easy or hard?
Count the Number of Incremovable Subarrays II is classified as a Hard problem because it requires recognizing structural properties of increasing sequences and designing a linear-time counting strategy using two pointers.
Count the Number of Incremovable Subarrays II Python/Java solution
Implementations typically compute the longest increasing prefix, then use two pointers to maintain a valid suffix while counting removable segments. The same algorithm works in Python, Java, C++, JavaScript, and other languages with O(n) time complexity.
How to solve Count the Number of Incremovable Subarrays II in O(n)?
First find the longest strictly increasing prefix. Then scan from the right to maintain a strictly increasing suffix. Use two pointers to connect valid prefix and suffix boundaries while ensuring nums[i] < nums[j]. Each valid pair defines multiple removable subarrays, allowing the total count to be computed in linear time.
What is the best approach for Count the Number of Incremovable Subarrays II?
The best approach uses a two-pointer sliding window after identifying the longest strictly increasing prefix and suffix. By maintaining valid prefix and suffix boundaries and ensuring nums[left] < nums[right], you can count all valid removable subarrays in O(n) time and O(1) space.
Is Count the Number of Incremovable Subarrays II asked at Google/Amazon/Meta?
Hard array and two-pointer problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. The problem tests understanding of monotonic properties, prefix/suffix reasoning, and efficient two-pointer scanning.
What data structure is used in Count the Number of Incremovable Subarrays II?
The core structure is a standard array combined with the two-pointer technique. Some implementations also use prefix and suffix helper arrays to track whether segments remain strictly increasing, and binary search can be applied when matching prefix and suffix boundaries.
What is the time complexity of Count the Number of Incremovable Subarrays II?
The optimal solution runs in O(n) time because each pointer moves across the array at most once. Space complexity can be O(1) with the two-pointer approach or O(n) if prefix and suffix helper arrays are used.