Count the Number of Incremovable Subarrays I — Easy Problem & Solution

A subarray is incremovable if removing it leaves the array strictly increasing.

Difficulty: Easy
Topics: Arrays, Two Pointers, Enumeration
Asked at: Amazon, Google, Wipro
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A subarray is incremovable if removing it leaves the array strictly increasing. The empty array counts as strictly increasing, and a subarray must be non-empty and contiguous.

Return the number of incremovable subarrays of nums.

Example 1

Input: nums = [1,2,3,4]
Output: 10
Explanation: Already increasing, so every one of the 10 subarrays qualifies.

Example 2

Input: nums = [6,5,7,8]
Output: 7
Explanation: Removing `[7]`, `[7,8]` or `[8]` leaves the `6,5` descent in place.

Example 3

Input: nums = [8,7,6,6]
Output: 3
Explanation: Only `[8,7,6]`, `[8,7,6,6]` and `[7,6,6]` work.

Constraints

1 <= nums.length <= 50
1 <= nums[i] <= 50

How to solve Count the Number of Incremovable Subarrays I

Enumerate every subarray [i..j] and check whether the concatenation of the untouched prefix and suffix is strictly increasing. At n <= 50 this direct check is fast enough, and it is the version of the problem where clarity beats cleverness.

Approach

For each pair i <= j, walk the array skipping indices i through j.
Track the previous surviving value and fail as soon as a value is not strictly greater.
Count the pairs that survive.

Why it works

Walking the array with the removed range skipped avoids building a new array per candidate, so the inner check is a single pass with no allocation. The linear-time solution required by version II instead finds the longest increasing prefix and suffix and pairs them with two pointers — but at this size the cubic enumeration is under 150 000 steps.

Complexity

Time — O(n³)
Space — O(1)

Pitfalls

The whole array is a valid subarray, and removing it leaves the empty array — which counts.
"Strictly" increasing: equal adjacent survivors fail.
The prefix and suffix must also be increasing across the join, not just internally.

Reference solution

Python

from typing import List

def incremovableSubarrayCount(nums: List[int]) -> int:
    n = len(nums)
    count = 0
    for i in range(n):
        for j in range(i, n):
            ok = True
            prev = -1
            for t in range(n):
                if i <= t <= j:
                    continue
                if prev != -1 and nums[t] <= prev:
                    ok = False
                    break
                prev = nums[t]
            if ok:
                count += 1
    return count

JavaScript

var incremovableSubarrayCount = function(nums) {
    var n = nums.length, count = 0;
    for (var i = 0; i < n; i++) {
        for (var j = i; j < n; j++) {
            var ok = true, prev = -1;
            for (var t = 0; t < n; t++) {
                if (t >= i && t <= j) continue;
                if (prev !== -1 && nums[t] <= prev) { ok = false; break; }
                prev = nums[t];
            }
            if (ok) count++;
        }
    }
    return count;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue