Skip to main content
Talentd

Count the Number of Incremovable Subarrays II - Solution & Explanation

HardArrayTwo PointersBinary Search23 min readAsked at: Apple, IBM, De Shaw
Practice this problem

Problem Statement

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 <= 105
  • 1 <= 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.

The code iterates through all possible subarrays and checks if the remaining elements form a strictly increasing sequence. It uses a nested loop to achieve this and increments the counter if the condition for a strictly increasing array holds.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^3) - The approach involves iterating over every possible subarray and checking its elements, resulting in a cubic complexity.
Space Complexity: O(1) - The algorithm only uses a fixed amount of additional space.

Try this approach in the editor →

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.

This C program uses two arrays, left and right, to store the longest increasing sequences from the start and end of the array, respectively. This allows concise calculations for potential removals and makes for a more efficient solution.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) - The approach involves linear scans and adds auxiliary space but avoids nested operations.
Space Complexity: O(n) - Two additional arrays of size n are required.

Try this approach in the editor →

Approach 3: Two Pointers

According to the problem description, after removing a subarray, the remaining elements are strictly increasing. Therefore, there are several situations:

  1. The remaining elements only include the prefix of the array nums (which can be empty);
  2. The remaining elements only include the suffix of the array nums;
  3. 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:

  1. The remaining elements only include the prefix of the array nums (which can be empty);
  2. 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:

  1. nums[i+1,...,n-1];
  2. nums[i,...,n-1];
  3. nums[i-1,...,n-1];
  4. nums[i-2,...,n-1];
  5. cdots;
  6. 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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window

Time Complexity: O(n^3) - The approach involves iterating over every possible subarray and checking its elements, resulting in a cubic complexity.
Space Complexity: O(1) - The algorithm only uses a fixed amount of additional space.

Efficient Linear Scan with Previous and Next Arrays

Time Complexity: O(n) - The approach involves linear scans and adds auxiliary space but avoids nested operations.
Space Complexity: O(n) - Two additional arrays of size n are required.

Two Pointers—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sliding Window with Two PointersO(n)O(1)Best general solution. Optimal for interviews and large inputs.
Prefix/Suffix Arrays + Linear ScanO(n)O(n)Useful when explicit prefix and suffix validity checks simplify reasoning.
Prefix with Binary Search on SuffixO(n log n)O(1)Good when suffix positions are pre-sorted and binary search is easier to implement.

Video Solution

Count the Number of Incremovable Subarrays II | Leetcode Biweekly 120 • codingMohan • 3,041 views views

Watch 2 more video solutions →

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.

Ready to solve this problem?

Practice Count the Number of Incremovable Subarrays II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Shortest Subarray to be Removed to Make Array Sorted