Count the number of incremovable subarrays i

Array Two Pointers Binary Search Enumeration

56.3% acceptance

Feb 25, 2026

198

125

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>) -> i32 {
    let n = nums.len();

    // Precompute: prefix[i] = true if nums[0..=i] is strictly increasing
    // suffix[i] = true if nums[i..n-1] is strictly increasing
    let strictly_inc = |arr: &[i32]| -> bool {
      arr.windows(2).all(|w| w[0] < w[1])
    };

    let mut ans = 0;
    for l in 0..n {
      for r in l..n {
        // Remove nums[l..=r], remaining = nums[0..l] + nums[r+1..n]
        let prefix = &nums[..l];
        let suffix = &nums[r + 1..];
        // Check: prefix is strictly increasing, suffix is strictly increasing,
        // and if both non-empty: last of prefix < first of suffix
        let ok = strictly_inc(prefix)
          && strictly_inc(suffix)
          && (prefix.is_empty()
            || suffix.is_empty()
            || prefix.last().unwrap() < suffix.first().unwrap());
        if ok {
          ans += 1;
        }
      }
    }
    ans
  }
}