Count the number of incremovable subarrays ii

Array Two Pointers Binary Search

40.1% acceptance

Feb 25, 2026

245

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. Return the total number of incremovable subarrays of nums.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn incremovable_subarray_count(nums: Vec<i32>) -> i64 {
    let n = nums.len();

    // l = length of strictly increasing prefix (nums[0..l-1] is strictly incr)
    let mut l = 1usize;
    while l < n && nums[l - 1] < nums[l] {
      l += 1;
    }

    // suf_start = start of strictly increasing suffix (nums[suf_start..n-1] is strictly incr)
    let mut suf_start = n - 1;
    while suf_start > 0 && nums[suf_start - 1] < nums[suf_start] {
      suf_start -= 1;
    }

    let mut ans = 0i64;

    // lo=0: all hi in [suf_start-1, n-1] are valid (or [0, n-1] if suf_start=0)
    let hi_min_lo0 = suf_start.saturating_sub(1);
    ans += (n - hi_min_lo0) as i64;

    // lo in 1..=l: two-pointer
    let mut hi_min = suf_start.saturating_sub(1);
    for lo in 1..=l {
      // Advance hi_min while nums[hi_min+1] <= nums[lo-1] (condition for no conflict)
      while hi_min < n - 1 && nums[hi_min + 1] <= nums[lo - 1] {
        hi_min += 1;
      }
      // hi must be >= lo (subarray [lo..hi] requires lo <= hi)
      let eff = hi_min.max(lo);
      if eff < n {
        ans += (n - eff) as i64;
      }
    }

    ans
  }
}