LeetCode 2970 - Count the Number of Incremovable Subarrays I

The problem asks us to count all subarrays of a given array nums such that if we remove the subarray, the remaining array becomes strictly increasing. A strictly increasing array is one where each element is less than the next element.

leetcodeeasyarraytwo-pointersbinary-searchenumeration

LeetCode Problem 2970

Difficulty: 🟢 Easy
Topics: Array, Two Pointers, Binary Search, Enumeration

Solution

Problem Understanding

The problem asks us to count all subarrays of a given array nums such that if we remove the subarray, the remaining array becomes strictly increasing. A strictly increasing array is one where each element is less than the next element. For example, [1,2,3] is strictly increasing, while [1,2,2] or [3,2,1] are not.

The input nums is a 0-indexed array of positive integers with length between 1 and 50, and each element is between 1 and 50. The output is a single integer representing the total number of subarrays that satisfy the incremovable property.

Key observations include:

  1. A subarray is contiguous, so we only consider slices of consecutive elements.
  2. The removal must result in a strictly increasing array. This includes the possibility that the removed subarray is at the start, middle, or end of the array.
  3. An empty array after removing a subarray is considered strictly increasing, so removing the entire array counts as one valid incremovable subarray.
  4. Edge cases involve arrays that are already strictly increasing or contain repeated elements that make parts non-increasing.

Constraints are small (n <= 50), so brute-force approaches are feasible, but we can still optimize.

Approaches

The brute-force approach is straightforward: generate all possible subarrays of nums, remove each subarray, and check if the resulting array is strictly increasing. This guarantees correctness because it checks every possibility.

However, this approach has a time complexity of O(n^3) because for each of the O(n^2) subarrays, we check if the remaining array is strictly increasing, which takes O(n) time. This is acceptable for n=50, but it is not elegant.

A more optimal approach leverages the fact that to check whether removing a subarray [i, j] makes the array strictly increasing, we only need to verify the boundary elements around the removed segment. Specifically, for removal of elements from index i to j:

  • Let left = nums[i-1] if i > 0 else -inf.
  • Let right = nums[j+1] if j < n-1 else inf.
  • If left < right, then removal of the subarray [i, j] preserves strict increase at the junction. We must also ensure all the elements before i and after j are strictly increasing.

This reduces unnecessary repeated checks and simplifies boundary verification.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(n) Check all subarrays and validate the remaining array for strict increase
Optimal O(n^2) O(n) Only check boundaries for strict increase, leveraging precomputed prefix/suffix arrays

Algorithm Walkthrough

  1. Compute prefix strictly increasing array pre where pre[i] is True if nums[0..i] is strictly increasing.
  2. Compute suffix strictly increasing array suf where suf[i] is True if nums[i..n-1] is strictly increasing.
  3. Iterate over all possible subarrays [i, j].
  4. For each subarray, check the following conditions:
  • pre[i-1] is True (if i > 0) to ensure the left part is strictly increasing.
  • suf[j+1] is True (if j < n-1) to ensure the right part is strictly increasing.
  • If i > 0 and j < n-1, also ensure nums[i-1] < nums[j+1] for the junction to be strictly increasing.
  1. Count the subarray if all conditions hold.
  2. Return the total count.

Why it works: By precomputing strictly increasing status for prefixes and suffixes, we avoid recomputing for each removal. Checking the boundary elements ensures that removing the subarray preserves strict increase at the junction, which is the only potential violation after removal.

Python Solution

from typing import List

class Solution:
    def incremovableSubarrayCount(self, nums: List[int]) -> int:
        n = len(nums)
        pre = [True] * n
        suf = [True] * n
        
        # compute prefix strictly increasing
        for i in range(1, n):
            pre[i] = pre[i-1] and nums[i-1] < nums[i]
        
        # compute suffix strictly increasing
        for i in range(n-2, -1, -1):
            suf[i] = suf[i+1] and nums[i] < nums[i+1]
        
        count = 0
        
        # iterate all subarrays
        for i in range(n):
            for j in range(i, n):
                left_ok = i == 0 or pre[i-1]
                right_ok = j == n-1 or suf[j+1]
                boundary_ok = True
                if i > 0 and j < n-1:
                    boundary_ok = nums[i-1] < nums[j+1]
                
                if left_ok and right_ok and boundary_ok:
                    count += 1
        
        return count

Implementation Walkthrough: We first build pre and suf arrays to quickly check whether the left and right segments are strictly increasing. Then we iterate through all subarrays [i, j] and check the three conditions: left part, right part, and boundary condition. Only if all are satisfied, we increment the counter. Finally, the counter is returned.

Go Solution

func incremovableSubarrayCount(nums []int) int {
    n := len(nums)
    pre := make([]bool, n)
    suf := make([]bool, n)
    
    for i := 0; i < n; i++ {
        pre[i] = true
        suf[i] = true
    }
    
    for i := 1; i < n; i++ {
        pre[i] = pre[i-1] && nums[i-1] < nums[i]
    }
    
    for i := n-2; i >= 0; i-- {
        suf[i] = suf[i+1] && nums[i] < nums[i+1]
    }
    
    count := 0
    for i := 0; i < n; i++ {
        for j := i; j < n; j++ {
            leftOk := i == 0 || pre[i-1]
            rightOk := j == n-1 || suf[j+1]
            boundaryOk := true
            if i > 0 && j < n-1 {
                boundaryOk = nums[i-1] < nums[j+1]
            }
            if leftOk && rightOk && boundaryOk {
                count++
            }
        }
    }
    
    return count
}

Go-specific notes: We preinitialize pre and suf slices to true. Boundary checks use slices carefully to avoid index out of range. Unlike Python, slices are zero-based and capacity handling is explicit, but logic mirrors Python closely.

Worked Examples

Example 1: nums = [1,2,3,4]

i j Left OK Right OK Boundary OK Count increment
0 0 True True True +1
0 1 True True True +1
0 2 True True True +1
0 3 True True True +1
1 1 True True True +1
1 2 True True True +1
1 3 True True True +1
2 2 True True True +1
2 3 True True True +1
3 3 True True True +1

Total count = 10

Example 2: nums = [6,5,7,8] calculation is similar.

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) Two nested loops over subarrays, prefix/suffix precomputation is O(n)
Space O(n) Two arrays pre and suf of size n

Given n <= 50, this is efficient.

Test Cases

# Provided examples
assert Solution().incremovableSubarrayCount([1,2,3,4]) == 10
assert Solution().incremovableSubarrayCount([6,5,7,8]) == 7
assert Solution().incremovableSubarrayCount([8,7,6,6]) == 3

# Edge cases
assert Solution().incremovableSubarrayCount([1]) == 1 # single element
assert Solution().incremovableSubarrayCount([1,1,1]) == 3 # all identical
assert Solution().incremovableSub