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

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

✓ Optimized

⏱️ Time: N/A Space: N/A

Brute Force - Check All Subarrays

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

For each possible subarray defined by start and end indices, remove it and check if the remaining array is strictly increasing. Count all valid removals.

Two Pointers with Prefix/Suffix

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

First identify the longest strictly increasing prefix and suffix. Then use two pointers to count all valid subarrays that can be removed while maintaining the increasing property.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

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

int 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 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)
    int 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 parseArray(char* line, int* arr) {
    int size = 0;
    int i = 0;
    int num = 0;
    int inNumber = 0;
    int negative = 0;
    
    while (line[i] != '\0' && line[i] != '\n') {
        if (line[i] >= '0' && line[i] <= '9') {
            if (!inNumber) {
                inNumber = 1;
                num = 0;
            }
            num = num * 10 + (line[i] - '0');
        } else if (line[i] == '-' && !inNumber) {
            negative = 1;
            inNumber = 1;
            num = 0;
        } else {
            if (inNumber) {
                arr[size++] = negative ? -num : num;
                inNumber = 0;
                negative = 0;
            }
        }
        i++;
    }
    
    if (inNumber) {
        arr[size++] = negative ? -num : num;
    }
    
    return size;
}

int main() {
    char line[10000];
    int nums[10000];
    
    fgets(line, sizeof(line), stdin);
    
    int n = parseArray(line, nums);
    
    printf("%d\n", solution(nums, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

⚠ Quadratic Growth

Space Complexity

✓ 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