incremovable subarray because after removing [8,7] nums becomes [6,6], which is sorted in ascending order but not strictly increasing.

Constraints

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9

Solution

Method 1 – Two Pointers and Binary Search

Intuition

A subarray is incremovable if, after removing it, the remaining array is strictly increasing. For large arrays, we can precompute the longest strictly increasing prefix and suffix, and for each possible subarray, check if removing it results in a strictly increasing array using binary search and two pointers.

Approach

Compute the longest strictly increasing prefix (pre) and suffix (suf).
For each possible left endpoint l, find the smallest right endpoint

Related Tags