Minimum array length after pair removals

Array Hash Table Two Pointers Binary Search Greedy Counting

27.1% acceptance

Feb 25, 2026

422

108

Given an integer array num sorted in non-decreasing order. You can perform the following operation any number of times: Choose two indices, i and j, where nums[i] < nums[j]. Then, remove the elements at indices i and j from nums. The remaining elements retain their original order, and the array is re-indexed. Return the minimum length of nums after applying the operation zero or more times.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_length_after_removals(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    // Max frequency of any element limits the answer
    let mut max_freq = 1usize;
    let mut cur_freq = 1usize;
    for i in 1..n {
      if nums[i] == nums[i-1] { cur_freq += 1; max_freq = max_freq.max(cur_freq); }
      else { cur_freq = 1; }
    }
    if max_freq > n / 2 { (2 * max_freq - n) as i32 } else { (n % 2) as i32 }
  }
}