Count the Number of Incremovable Subarrays I

Count the Number of Incremovable Subarrays I - Problem

You are given a 0-indexed array of positive integers nums. A subarray of nums is called incremovable if nums becomes strictly increasing after 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.

Input & Output

Example 1 — Basic Case

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

› Output: 6

💡 Note: The 6 incremovable subarrays are: [3], [4], [3,4], [3,4,6], [3,4,6,7], [6,7]. After removing any of these, the remaining array is strictly increasing.

Example 2 — Already Sorted

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

› Output: 10

💡 Note: Since the array is already strictly increasing, we can remove any subarray. Total subarrays = n(n+1)/2 = 4×5/2 = 10.

Example 3 — Minimum Size

$ Input: nums = [6,5]

› Output: 3

💡 Note: We can remove [6], [5], or [6,5]. All result in strictly increasing (or empty) arrays.

Constraints

1 ≤ nums.length ≤ 50
1 ≤ nums[i] ≤ 50

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array [5,3,4,6,7] with mixed order

Try Removals

Test removing different contiguous subarrays

Count Valid

Count subarrays whose removal makes array strictly increasing

Key Takeaway

🎯 Key Insight: An incremovable subarray creates a strictly increasing remainder when the left and right parts connect properly

Asked in

M Microsoft 8 G Google 5

The key insight is to identify the longest strictly increasing prefix and suffix, then count valid ways to connect them after removing middle elements. The optimal approach runs in O(n) time by using two pointers to efficiently count combinations. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Single Pass	O(n)	O(1)	Count incremovable subarrays by analyzing prefix and suffix in one pass
Two Pointers Optimization	O(n²)	O(1)	Find longest increasing prefix and suffix, then count valid combinations
Brute Force	O(n³)	O(n)	Try removing every possible subarray and check if remainder is strictly increasing

Optimized Single Pass — Algorithm Steps

Single pass to find prefix and suffix boundaries
Handle special case: entire array is sorted
Count prefix-only removals
Count suffix-only removals
Count prefix-suffix combinations using two pointers

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Boundaries

Single scan identifies prefix and suffix limits

Count Cases

Separate counting for different removal types

Combine Results

Sum all valid incremovable subarray counts

Code -

solution.c — C

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

int solution(int* nums, int n) {
    // Find the longest strictly increasing prefix
    int left = 0;
    while (left < n - 1 && nums[left] < nums[left + 1]) {
        left++;
    }
    
    // If the entire array is strictly increasing
    if (left == n - 1) {
        return n * (n + 1) / 2;
    }
    
    // Find the longest strictly increasing suffix
    int right = n - 1;
    while (right > 0 && nums[right - 1] < nums[right]) {
        right--;
    }
    
    // Count the incremovable subarrays
    int count = (left + 2) + (n - right);  // prefix + suffix cases
    
    // Two pointers to count valid prefix-suffix combinations
    int i = 0, j = right;
    while (i <= left && j < n) {
        if (nums[i] < nums[j]) {
            count += n - j;
            i++;
        } else {
            j++;
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    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, "[,]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to find prefix/suffix boundaries, then two-pointer technique to count combinations in O(n) time

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for pointers and counters

✓ Linear Space

12.5K Views

Medium Frequency

~25 min Avg. Time

234 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

Optimized Single Pass — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler