Minimum number of increasing subsequence to be removed

Array Binary Search

46.6% acceptance

Mar 31, 2026

Given an array of integers nums, you are allowed to perform the following operation any number of times: Remove a strictly increasing subsequence from the array. Your task is to find the minimum number of operations required to make the array empty.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

use std::collections::BTreeMap;

impl Solution {
  pub fn min_operations(nums: Vec<i32>) -> i32 {
    let mut map: BTreeMap<i32, i32> = BTreeMap::new();
    for num in nums {
      let key = map.range(..num).next_back().map(|(&k, _)| k);
      if let Some(k) = key {
        let count = map.get_mut(&k).unwrap();
        *count -= 1;
        if *count == 0 {
          map.remove(&k);
        }
      }
      *map.entry(num).or_insert(0) += 1;
    }
    map.values().sum()
  }
}