Sorting three groups

Array Binary Search Dynamic Programming

42.9% acceptance

Feb 25, 2026

525

You are given an integer array nums. Each element in nums is 1, 2 or 3. In each operation, you can remove an element from nums. Return the minimum number of operations to make nums non-decreasing.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_operations(nums: Vec<i32>) -> i32 {
    // dp[v] = length of longest non-decreasing subsequence ending with value v
    let mut dp = [0i32; 4];
    for &v in &nums {
      let v = v as usize;
      let best = *dp[1..=v].iter().max().unwrap();
      dp[v] = dp[v].max(best + 1);
    }
    nums.len() as i32 - *dp[1..=3].iter().max().unwrap()
  }
}