Count the Number of Incremovable Subarrays II

Count the Number of Incremovable Subarrays II - 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: An empty array is considered strictly increasing. A subarray is a contiguous non-empty sequence of elements within an array.

Input & Output

Example 1 — Mixed Array

$ Input: nums = [5,3,4,6,7]

› Output: 9

💡 Note: We can remove subarrays like [3], [4], [3,4], [3,4,6], [3,4,6,7], [4,6], [4,6,7], [6,7], [7] to make remaining array strictly increasing.

Example 2 — Already Sorted

$ Input: nums = [1,2,3,4,5]

› Output: 15

💡 Note: Array is already strictly increasing, so any subarray can be removed. Total = 5×6/2 = 15 subarrays.

Example 3 — Small Array

$ Input: nums = [6,5,7,8]

› Output: 7

💡 Note: Can remove [5], [6], [6,5], [5,7], [6,5,7], [5,7,8], [6,5,7,8] to get strictly increasing arrays.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

[5,3,4,6,7] with mixed increasing/decreasing sections

Try Removals

Test removing various subarrays and check if remainder is sorted

Count Valid

Total of 9 different subarrays can be removed

Key Takeaway

🎯 Key Insight: Use prefix/suffix analysis with two pointers to efficiently count valid removals without testing each one

Asked in

G Google 15 f Meta 12

The key insight is to identify the longest strictly increasing prefix and suffix, then use two pointers to efficiently count valid subarray removals. The optimal two-pointer approach runs in O(n) time by avoiding redundant checks. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers with Prefix/Suffix	O(n)	O(1)	Find longest increasing prefix and suffix, then efficiently count valid removals
Brute Force - Check All Subarrays	O(n³)	O(1)	Try removing every possible subarray and check if remaining array is strictly increasing

Two Pointers with Prefix/Suffix — Algorithm Steps

Find longest increasing prefix from start
Find longest increasing suffix from end
Use two pointers to count valid removals between prefix and suffix
Handle special cases where entire array or middle section is removed

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Prefix

Identify longest increasing prefix [5] and suffix [6,7]

Two Pointers

Use pointers to count valid combinations

Count Total

Sum all valid removal possibilities

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

long long solution(int* nums, int n) {
    // Find longest strictly increasing prefix
    int prefixLen = 1;
    while (prefixLen < n && nums[prefixLen] > nums[prefixLen - 1]) {
        prefixLen++;
    }
    
    // If entire array is strictly increasing, we can remove any subarray
    if (prefixLen == n) {
        return (long long) n * (n + 1) / 2;
    }
    
    // Find longest strictly increasing suffix
    int suffixStart = n - 1;
    while (suffixStart > 0 && nums[suffixStart - 1] < nums[suffixStart]) {
        suffixStart--;
    }
    
    // Count removals: all prefix + 1 (remove suffix), all suffix + 1 (remove prefix)
    long long count = prefixLen + 1 + (n - suffixStart + 1);
    
    // Use two pointers to count removals that keep both prefix and suffix
    int left = 0;
    int right = suffixStart;
    
    while (left < prefixLen && right < n) {
        if (nums[left] < nums[right]) {
            count += n - right;
            left++;
        } else {
            right++;
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int num = atoi(token);
        if (num != 0 || token[0] == '0') {
            nums[n++] = num;
        }
        token = strtok(NULL, "[,]");
    }
    
    long long result = solution(nums, n);
    printf("%lld\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to find prefix/suffix, then two-pointer traversal

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for pointers and counters

✓ Linear Space

12.0K Views

Medium Frequency

~35 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers with Prefix/Suffix — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler