Minimum pair removal to sort array i

Array Hash Table Linked List Heap (Priority Queue) Simulation Doubly-Linked List Ordered Set

65.3% acceptance

Feb 25, 2026

487

Given an array nums, you can perform the following operation any number of times: Select the adjacent pair with the minimum sum in nums. If multiple such pairs exist, choose the leftmost one. Replace the pair with their sum. Return the minimum number of operations needed to make the array non-decreasing. An array is said to be non-decreasing if each element is greater than or equal to its previous element (if it exists).

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_pair_removal(nums: Vec<i32>) -> i32 {
    let mut arr: Vec<i64> = nums.iter().map(|&x| x as i64).collect();
    let mut ops = 0;

    loop {
      // Check if non-decreasing
      if arr.windows(2).all(|w| w[0] <= w[1]) { break; }

      // Find leftmost pair with minimum sum
      let (min_sum, min_idx) = arr.windows(2)
        .enumerate()
        .map(|(i, w)| (w[0] + w[1], i))
        .min_by(|a, b| a.0.cmp(&b.0).then(a.1.cmp(&b.1)))
        .unwrap();

      // Merge pair at min_idx
      arr[min_idx] = min_sum;
      arr.remove(min_idx + 1);
      ops += 1;
    }

    ops
  }
}