Problem Description

You are given a 0-indexed array of positive integers nums.

A subarray is called incremovable if removing it from nums results in the remaining array being strictly increasing. For example, in the array [5, 3, 4, 6, 7], the subarray [3, 4] is incremovable because removing it gives us [5, 6, 7], which is strictly increasing.

Your task is to count the total number of incremovable subarrays in nums.

Key points to understand:

• A subarray is a contiguous non-empty sequence of elements
• An empty array is considered strictly increasing
• Strictly increasing means each element is strictly greater than the previous one (no equal values allowed)

The solution uses a two-pointer approach to handle two main scenarios:

1. Removing subarrays from the end: After removal, only a prefix of the original array remains. The code finds the longest strictly increasing prefix using pointer i. If the entire array is already strictly increasing (when i == n-1), then any subarray can be removed, giving us n * (n + 1) // 2 total subarrays.

2. Removing subarrays from the middle: After removal, we keep both a prefix and a suffix of the original array. The code uses pointer j to iterate through possible suffix starting positions from right to left. For each valid suffix position, it adjusts pointer i to find the longest prefix where nums[i] < nums[j], ensuring the combined prefix and suffix form a strictly increasing sequence.

The algorithm counts all valid subarrays whose removal maintains the strictly increasing property by considering both cases: removing from the end (counted as i + 2 subarrays) and removing from the middle while maintaining valid prefix-suffix combinations.

Intuition

The key insight is to think about what remains after removing a subarray, rather than what we remove. When we remove a contiguous subarray, we're left with either:

• Nothing (remove everything)
• Only a prefix of the original array
• Only a suffix of the original array
• Both a prefix and a suffix (with a gap in the middle)

For the result to be strictly increasing, whatever remains must form a strictly increasing sequence.

Let's start with the simplest case: if the entire array is already strictly increasing, then removing ANY subarray will leave us with a strictly increasing result (or empty, which counts as strictly increasing). This gives us n * (n + 1) // 2 total subarrays.

For the general case, we need to identify valid prefixes and suffixes that can be kept. A valid prefix is one that is strictly increasing from the start. Similarly, a valid suffix is one that is strictly increasing to the end.

The crucial observation is that we can categorize all removals into two types:

1. Remove everything from some point onwards - keeping only a prefix
2. Remove a middle portion - keeping both a prefix and a suffix

For type 1, if we have a strictly increasing prefix of length i+1 (indices 0 to i), we can remove:

• Everything from index i+1 onwards: [i+1, n-1]
• Everything from index i onwards: [i, n-1]
• Everything from index i-1 onwards: [i-1, n-1]
• And so on, down to removing the entire array [0, n-1]

This gives us i + 2 possible removals.

For type 2, we need to ensure that when we keep both a prefix and suffix, the last element of the prefix is less than the first element of the suffix (to maintain strict increasing property). We iterate through possible suffix starting points from right to left. For each suffix starting at position j, we find the longest valid prefix where nums[i] < nums[j]. Each such valid combination allows i + 2 different removals (we can start removing from any position from 0 to i+1, and end just before j).

The algorithm efficiently counts both types by first finding the longest increasing prefix, then iterating through valid suffixes while adjusting the prefix pointer to maintain the strictly increasing property between prefix and suffix.

Learn more about Two Pointers and Binary Search patterns.

Solution Approach

The implementation uses a two-pointer technique to efficiently count all incremovable subarrays. Here's how the algorithm works step by step:

Step 1: Find the longest strictly increasing prefix

i, n = 0, len(nums)
while i + 1 < n and nums[i] < nums[i + 1]:
    i += 1

We use pointer i to find the last index of the longest strictly increasing prefix. This prefix spans from index 0 to index i.

Step 2: Handle the special case - entire array is strictly increasing

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

If i reaches n-1, the entire array is already strictly increasing. In this case, any subarray can be removed and the result will still be strictly increasing (or empty). The total number of subarrays in an array of length n is n * (n + 1) // 2.

Step 3: Count subarrays that leave only a prefix

ans = i + 2

For the general case, we first count all subarrays whose removal leaves only a prefix (or nothing). These are:

• Remove nums[i+1,...,n-1] (keep prefix up to index i)
• Remove nums[i,...,n-1] (keep prefix up to index i-1)
• Remove nums[i-1,...,n-1] (keep prefix up to index i-2)
• ... and so on
• Remove nums[0,...,n-1] (keep nothing)

This gives us i + 2 possible removals.

Step 4: Count subarrays that leave both prefix and suffix

j = n - 1
while j:
    while i >= 0 and nums[i] >= nums[j]:
        i -= 1
    ans += i + 2
    if nums[j - 1] >= nums[j]:
        break
    j -= 1

We use pointer j to iterate through possible suffix starting positions from right to left:

• Start with j = n - 1 (suffix contains only the last element)
• For each suffix starting at j, adjust pointer i leftward until we find the longest prefix where nums[i] < nums[j]
• This ensures that concatenating the prefix nums[0...i] with the suffix nums[j...n-1] results in a strictly increasing sequence
• For each valid (i, j) pair, we can remove subarrays starting from any position from 0 to i+1 and ending at j-1, giving us i + 2 more valid removals
• We stop when nums[j-1] >= nums[j], as the suffix would no longer be strictly increasing if we include nums[j-1]

The algorithm efficiently counts all valid incremovable subarrays in O(n) time using two pointers, avoiding the need to check every possible subarray individually.

Example Walkthrough

Let's walk through the algorithm with the array nums = [1, 2, 3, 6, 5, 7].

Step 1: Find the longest strictly increasing prefix

• Start with i = 0
• Check: nums[0] < nums[1] → 1 < 2 ✓, so i = 1
• Check: nums[1] < nums[2] → 2 < 3 ✓, so i = 2
• Check: nums[2] < nums[3] → 3 < 6 ✓, so i = 3
• Check: nums[3] < nums[4] → 6 < 5 ✗, stop

The longest strictly increasing prefix is [1, 2, 3, 6] with i = 3.

Step 2: Check if entire array is strictly increasing

• Since i = 3 and n - 1 = 5, we have i ≠ n - 1
• The array is not entirely strictly increasing, so we continue.

Step 3: Count removals that leave only a prefix (or nothing)

• ans = i + 2 = 3 + 2 = 5

These 5 removals are:

1. Remove [5, 7] (indices 4-5) → Keep [1, 2, 3, 6] ✓
2. Remove [6, 5, 7] (indices 3-5) → Keep [1, 2, 3] ✓
3. Remove [3, 6, 5, 7] (indices 2-5) → Keep [1, 2] ✓
4. Remove [2, 3, 6, 5, 7] (indices 1-5) → Keep [1] ✓
5. Remove [1, 2, 3, 6, 5, 7] (indices 0-5) → Keep [] ✓

Step 4: Count removals that leave both prefix and suffix

Initialize j = 5 (last index), suffix is [7].

First iteration (j = 5):

• Current suffix: [7]
• Adjust i: Check if nums[3] >= nums[5] → 6 >= 7 ✗, so i stays at 3
• Valid prefix: [1, 2, 3, 6], valid suffix: [7]
• Since nums[3] < nums[5] (6 < 7), concatenation gives [1, 2, 3, 6, 7] ✓
• Add i + 2 = 3 + 2 = 5 to answer
• ans = 5 + 5 = 10

These 5 additional removals are:

1. Remove [5] (index 4) → Keep [1, 2, 3, 6, 7] ✓
2. Remove [6, 5] (indices 3-4) → Keep [1, 2, 3, 7] ✓
3. Remove [3, 6, 5] (indices 2-4) → Keep [1, 2, 7] ✓
4. Remove [2, 3, 6, 5] (indices 1-4) → Keep [1, 7] ✓
5. Remove [1, 2, 3, 6, 5] (indices 0-4) → Keep [7] ✓

Check next iteration:

• Check if nums[4] >= nums[5] → 5 >= 7 ✗
• Move to j = 4

Second iteration (j = 4):

• Current suffix would be [5, 7]
• Need to adjust i until nums[i] < nums[4] → nums[i] < 5
• Check nums[3] >= nums[4] → 6 >= 5 ✓, so i = 2
• Check nums[2] >= nums[4] → 3 >= 5 ✗, so i stays at 2
• Valid prefix: [1, 2, 3], valid suffix: [5, 7]
• Since nums[2] < nums[4] (3 < 5), concatenation gives [1, 2, 3, 5, 7] ✓
• Add i + 2 = 2 + 2 = 4 to answer
• ans = 10 + 4 = 14

These 4 additional removals are:

1. Remove [6] (index 3) → Keep [1, 2, 3, 5, 7] ✓
2. Remove [3, 6] (indices 2-3) → Keep [1, 2, 5, 7] ✓
3. Remove [2, 3, 6] (indices 1-3) → Keep [1, 5, 7] ✓
4. Remove [1, 2, 3, 6] (indices 0-3) → Keep [5, 7] ✓

Check next iteration:

• Check if nums[3] >= nums[4] → 6 >= 5 ✓
• This means extending the suffix further left would break the strictly increasing property
• Stop the algorithm

Final Answer: 14 incremovable subarrays

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums.

The algorithm consists of:

• First while loop: Traverses from the beginning of the array until it finds a non-increasing element or reaches the end. This takes at most O(n) time.
• If the entire array is strictly increasing (checked by i == n - 1), it returns immediately with O(1) calculation.
• Second while loop (outer): Starts from j = n - 1 and decrements j. In the worst case, it runs O(n) times.
• Inner while loop: The key insight is that i only decrements throughout the entire execution. Since i starts at most at position n-1 and can only decrease to -1, the total number of decrements across all iterations of the outer loop is bounded by n. Therefore, the amortized cost is O(1) per outer loop iteration.

Overall, the total time complexity is O(n) + O(n) = O(n).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space:

• Variables i, j, n, and ans are all integer variables.
• No additional data structures are created.
• The space used does not depend on the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Errors in Counting

One of the most common mistakes is incorrectly calculating the number of valid subarrays for each configuration. When we have a valid prefix ending at index i, the count should be i + 2 (not i + 1), because:

• We can remove from index 0 to some point (gives us i + 1 options)
• Plus we can remove everything (empty prefix case)

Incorrect approach:

result = i + 1  # Missing the empty prefix case

Correct approach:

result = i + 2  # Includes all valid removal options

2. Not Handling the Strictly Increasing Check Properly

A critical pitfall is using <= instead of < when checking for strictly increasing sequences. The problem requires strictly increasing arrays, meaning no equal consecutive elements.

Incorrect approach:

# Wrong: allows equal elements
while left_boundary + 1 < array_length and nums[left_boundary] <= nums[left_boundary + 1]:
    left_boundary += 1

Correct approach:

# Correct: ensures strictly increasing
while left_boundary + 1 < array_length and nums[left_boundary] < nums[left_boundary + 1]:
    left_boundary += 1

3. Forgetting to Break When Suffix is No Longer Valid

When iterating through suffixes, failing to check if the suffix remains strictly increasing can lead to incorrect counts. Once nums[j-1] >= nums[j], extending the suffix leftward would violate the strictly increasing property.

Incorrect approach:

while right_boundary > 0:
    # ... counting logic ...
    right_boundary -= 1
    # Missing the check for valid suffix extension

Correct approach:

while right_boundary > 0:
    # ... counting logic ...
    if nums[right_boundary - 1] >= nums[right_boundary]:
        break  # Stop when suffix can't be extended
    right_boundary -= 1

4. Misunderstanding the Two-Pointer Logic

A subtle but important pitfall is not understanding why we move left_boundary backward in the second phase. The pointer left_boundary needs to be adjusted for each new suffix position to find the maximum valid prefix that can connect with that suffix.

Key insight: For each suffix starting at j, we need the largest i such that nums[i] < nums[j] to maximize the count of valid removals. This is why we only move left_boundary leftward (never rightward) in the second phase.

5. Edge Case: Single Element Array

While the provided solution handles this correctly, it's worth noting that for a single-element array [x], the only subarray is [x] itself, and removing it leaves an empty array (which is considered strictly increasing). The formula n * (n + 1) // 2 correctly gives us 1 for this case.