LeetCode 2972 - Count the Number of Incremovable Subarrays II

The problem gives us an array nums of positive integers and asks us to count how many contiguous non-empty subarrays can be removed so that the remaining elements form a strictly increasing array.

leetcodehardarraytwo-pointersbinary-search

LeetCode Problem 2972

Difficulty: 🔴 Hard
Topics: Array, Two Pointers, Binary Search

Solution

Problem Understanding

The problem gives us an array nums of positive integers and asks us to count how many contiguous non-empty subarrays can be removed so that the remaining elements form a strictly increasing array.

A strictly increasing array means that every adjacent pair satisfies:

$a_i < a_{i+1}$

When we remove a subarray, the remaining elements are the prefix before the removed section and the suffix after the removed section, joined together. The resulting array must still preserve strict increasing order across every remaining adjacent pair.

For example, if:

nums = [5,3,4,6,7]

and we remove [3,4], the remaining array becomes:

[5,6,7]

which is strictly increasing, so [3,4] is incremovable.

The important detail is that the removed subarray itself does not need to be increasing. Only the remaining array matters.

The constraints are large:

1 <= nums.length <= 100000

This immediately tells us that quadratic or cubic solutions will be too slow. Any algorithm that checks all subarrays individually and validates the remainder from scratch will exceed time limits.

There are several edge cases that are important:

  • The entire array may already be strictly increasing. In that case, every possible subarray removal works.
  • The array may contain equal adjacent values, which violate strict increasing order.
  • Removing the entire array is allowed because the empty array is considered strictly increasing.
  • Very small arrays, especially length 1, require careful handling because every subarray removal leaves an empty array.

The core challenge is efficiently determining which removals preserve strict increasing order in the remaining elements.

Approaches

Brute Force

The brute force approach tries every possible subarray removal.

For every pair (l, r) representing the subarray nums[l:r+1], we remove that section and check whether the remaining array is strictly increasing.

The remaining array consists of:

nums[0:l] + nums[r+1:n]

To validate it, we scan the remaining elements and verify that every adjacent pair is strictly increasing.

This approach is correct because it explicitly checks every possible removal and directly verifies the required condition.

However, the complexity is far too high. There are:

O(n^2)

possible subarrays, and validating each one takes:

O(n)

time in the worst case.

That gives a total complexity of:

O(n^3)

which is impossible for n = 100000.

Optimal Insight

The key observation is that after removing a subarray, the remaining array is made from:

  1. A prefix
  2. A suffix

Both remaining parts must already be strictly increasing individually, and the boundary between them must also remain increasing.

Suppose we remove:

nums[i+1 : j-1]

Then the remaining array is:

nums[0:i] + nums[j:n-1]

For this to be strictly increasing:

  1. The prefix nums[0:i] must be strictly increasing.
  2. The suffix nums[j:n-1] must be strictly increasing.
  3. If both sides exist, then:

$nums[i] < nums[j]$

must hold.

This allows us to avoid checking every removal explicitly.

We first identify the longest strictly increasing prefix and suffix. Then we use a two pointer technique to efficiently count valid combinations.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(1) Checks every subarray and validates remaining array
Optimal O(n) O(1) Uses increasing prefix/suffix structure with two pointers

Algorithm Walkthrough

Step 1: Find the longest strictly increasing prefix

Start from index 0 and move right while:

$nums[i-1] < nums[i]$

holds.

Let the final index be left.

This means:

nums[0:left]

is strictly increasing.

If left == n - 1, then the entire array is already strictly increasing.

In that case, every subarray removal works.

The number of subarrays in an array of length n is:

$\frac{n(n+1)}{2}$

so we return that immediately.

Step 2: Initialize answer using suffix-only removals

If we remove a prefix and keep only a suffix, the suffix itself must be strictly increasing.

Every removal starting from index 0 and ending before or at left is valid.

We initialize:

answer = left + 2

This counts all removals where the remaining array is only a suffix.

Step 3: Traverse strictly increasing suffix

Now we move from the right side toward the left while the suffix remains strictly increasing.

Suppose right is the start index of the suffix.

Then:

nums[right:n]

is strictly increasing.

Step 4: Adjust left pointer

For the current suffix beginning at right, we need to find how many prefixes can connect to it.

We move left backward while:

$nums[left] \ge nums[right]$

because such prefixes cannot connect to the suffix while preserving strict increase.

Step 5: Count valid prefixes

After adjustment, every prefix ending at indices:

-1, 0, 1, ..., left

can connect to the suffix.

The -1 case represents removing the entire prefix before right.

So the number of valid choices is:

left + 2

Add this to the answer.

Step 6: Continue until suffix stops increasing

Move right leftward while the suffix remains strictly increasing.

Once the suffix itself is no longer strictly increasing, we stop.

Why it works

The algorithm works because every valid remaining array must consist of:

  1. A strictly increasing prefix
  2. A strictly increasing suffix
  3. A valid bridge where the last prefix element is smaller than the first suffix element

The two pointer method efficiently enumerates all such compatible prefix/suffix combinations exactly once.

Because both pointers move only in one direction, the total work is linear.

Python Solution

from typing import List

class Solution:
    def incremovableSubarrayCount(self, nums: List[int]) -> int:
        n = len(nums)

        left = 0

        while left + 1 < n and nums[left] < nums[left + 1]:
            left += 1

        if left == n - 1:
            return n * (n + 1) // 2

        answer = left + 2

        right = n - 1

        while right == n - 1 or nums[right] < nums[right + 1]:

            while left >= 0 and nums[left] >= nums[right]:
                left -= 1

            answer += left + 2

            right -= 1

        return answer

The implementation begins by finding the longest strictly increasing prefix. The variable left stores the ending index of that prefix.

If the whole array is increasing, the solution immediately returns the total number of subarrays using the standard formula.

Otherwise, the algorithm initializes the answer with all valid removals that leave only a suffix.

The right pointer then traverses the strictly increasing suffix from right to left. For each suffix, the left pointer moves backward until the boundary condition:

nums[left] < nums[right]

becomes true.

At that point, all prefixes from -1 through left are compatible with the suffix, so we add left + 2 to the answer.

Because each pointer moves only once across the array, the algorithm runs in linear time.

Go Solution

func incremovableSubarrayCount(nums []int) int64 {
	n := len(nums)

	left := 0

	for left+1 < n && nums[left] < nums[left+1] {
		left++
	}

	if left == n-1 {
		return int64(n * (n + 1) / 2)
	}

	var answer int64 = int64(left + 2)

	right := n - 1

	for right == n-1 || nums[right] < nums[right+1] {

		for left >= 0 && nums[left] >= nums[right] {
			left--
		}

		answer += int64(left + 2)

		right--
	}

	return answer
}

The Go implementation follows the same logic as the Python version.

One important detail is integer handling. The number of valid subarrays can be as large as:

$\frac{100000 \times 100001}{2}$

which exceeds 32-bit integer range, so the answer uses int64.

Go slices are already reference-based, so no additional memory allocation is needed.

Worked Examples

Example 1

nums = [1,2,3,4]

Step 1: Find increasing prefix

Index Comparison Result
0 1 < 2 valid
1 2 < 3 valid
2 3 < 4 valid

So:

left = 3

Since left == n - 1, the entire array is strictly increasing.

Total subarrays:

$\frac{4 \times 5}{2}$

Result:

10

Example 2

nums = [6,5,7,8]

Step 1: Find increasing prefix

Index Comparison Result
0 6 < 5 false

So:

left = 0

Initial answer:

answer = left + 2 = 2

Step 2: Traverse suffixes

right = 3

Suffix:

[8]

Check bridge:

nums[0] = 6 < 8

Valid.

Add:

left + 2 = 2

Now:

answer = 4

right = 2

Suffix:

[7,8]

Check:

6 < 7

Valid.

Add 2.

answer = 6

right = 1

Suffix:

[5,7,8]

Now:

6 >= 5

Move left:

left = -1

Add:

left + 2 = 1

Final answer:

7

Example 3

nums = [8,7,6,6]

Step 1: Increasing prefix

8 < 7 is false

So:

left = 0

Initial answer:

2

Step 2: Traverse suffix

right = 3

Suffix:

[6]

Bridge:

8 >= 6

Move left to -1.

Add:

1

Answer becomes:

3

right = 2

Check suffix condition:

6 < 6 is false

Stop.

Final answer:

3

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each pointer moves at most once
Space O(1) Only a few variables are used

The algorithm is linear because both left and right pointers move monotonically. Neither pointer ever resets or revisits indices, so the total number of operations is proportional to the array length.

The solution uses constant extra memory because no auxiliary arrays or data structures are needed.

Test Cases

from typing import List

class Solution:
    def incremovableSubarrayCount(self, nums: List[int]) -> int:
        n = len(nums)

        left = 0

        while left + 1 < n and nums[left] < nums[left + 1]:
            left += 1

        if left == n - 1:
            return n * (n + 1) // 2

        answer = left + 2

        right = n - 1

        while right == n - 1 or nums[right] < nums[right + 1]:

            while left >= 0 and nums[left] >= nums[right]:
                left -= 1

            answer += left + 2

            right -= 1

        return answer

sol = Solution()

assert sol.incremovableSubarrayCount([1,2,3,4]) == 10  # already increasing
assert sol.incremovableSubarrayCount([6,5,7,8]) == 7  # one inversion
assert sol.incremovableSubarrayCount([8,7,6,6]) == 3  # duplicates break strictness
assert sol.incremovableSubarrayCount([1]) == 1  # single element
assert sol.incremovableSubarrayCount([1,2]) == 3  # fully increasing size 2
assert sol.incremovableSubarrayCount([2,1]) == 3  # all removals valid
assert sol.incremovableSubarrayCount([1,1,1]) == 3  # equal values
assert sol.incremovableSubarrayCount([1,3,2,4]) == 8  # middle inversion
assert sol.incremovableSubarrayCount([5,4,3,2,1]) == 3  # strictly decreasing
assert sol.incremovableSubarrayCount([1,2,3,2,4]) == 11  # longer mixed case

Test Case Summary

Test Why
[1,2,3,4] Entire array already increasing
[6,5,7,8] Single inversion near beginning
[8,7,6,6] Duplicate values violate strictness
[1] Smallest possible input
[1,2] Small increasing array
[2,1] Small decreasing array
[1,1,1] All equal elements
[1,3,2,4] Inversion in middle
[5,4,3,2,1] Completely decreasing array
[1,2,3,2,4] Complex mixed ordering

Edge Cases

Entire Array Already Strictly Increasing

If the array is already strictly increasing, every subarray removal is valid because removing elements from an increasing sequence cannot introduce a violation.

This case is important because the optimal algorithm uses a special early return. Without it, the counting logic would become more complicated and could double count cases.

The implementation handles this by checking whether the increasing prefix reaches the final index.

Arrays With Duplicate Values

Strictly increasing means adjacent values must satisfy:

$a_i < a_{i+1}$

Equality is not allowed.

Arrays like:

[1,1,1]

are especially tricky because many naive implementations accidentally treat them as non-decreasing instead of strictly increasing.

The solution correctly uses < everywhere and never uses <=.

Completely Decreasing Arrays

Arrays such as:

[5,4,3,2,1]

have almost no valid remaining prefixes or suffixes.

This case stresses the pointer movement logic because the left pointer quickly becomes -1.

The implementation safely handles this by allowing left = -1, which represents choosing an empty prefix. The counting formula left + 2 naturally accounts for this situation without requiring special handling.