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,6], [3,4,6,7], [5,3], [5,3,4], [5,3,4,6]. 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

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

✓ Brute Force

⏱️ Time: O(n³) Space: O(n)

Generate all possible subarrays, remove each one, and check if the remaining array is strictly increasing. For each starting position i and ending position j, create a new array without elements from i to j and verify if it's sorted.

Optimized Single Pass

⏱️ Time: O(n) Space: O(1)

Use a single pass to identify the structure of the array and directly count valid removals. Handle the special case where the entire array is already sorted separately, then count removals efficiently.

Two Pointers Optimization

⏱️ Time: O(n²) Space: O(1)

Instead of checking every removal, find the longest strictly increasing prefix and suffix. Then count how many ways we can remove middle elements while keeping valid connections between prefix and suffix.

Brute Force — Algorithm Steps

Generate all possible subarrays with start i and end j
For each subarray, create remainder by excluding elements i to j
Check if remainder array is strictly increasing
Count all valid removals

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subarrays

Create all possible contiguous subarrays to remove

Create Remainder

Form new array without the removed subarray

Check Sorted

Verify if remainder is strictly increasing

Code -

solution.c — C

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

int solution(int* nums, int n) {
    int count = 0;
    
    // Try removing subarray from i to j (inclusive)
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            // Create remainder array without elements from i to j
            int remainder[1000];
            int remainderSize = 0;
            
            for (int k = 0; k < i; k++) {
                remainder[remainderSize++] = nums[k];
            }
            for (int k = j + 1; k < n; k++) {
                remainder[remainderSize++] = nums[k];
            }
            
            // Check if remainder is strictly increasing
            bool isIncreasing = true;
            for (int k = 1; k < remainderSize; k++) {
                if (remainder[k] <= remainder[k-1]) {
                    isIncreasing = false;
                    break;
                }
            }
            
            if (isIncreasing) {
                count++;
            }
        }
    }
    
    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, "[,]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Nested loops to generate O(n²) subarrays, each taking O(n) to verify if remaining array is sorted

✓ Linear Growth

Space Complexity

O(n)

Need to store remainder array for each subarray check

✓ 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

Count the Number of Incremovable Subarrays I - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler