Minimum pair removal to sort array ii

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

39.2% acceptance

Feb 25, 2026

404

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(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_pair_removal(nums: Vec<i32>) -> i32 {
    use std::collections::BinaryHeap;
    use std::cmp::Reverse;

    let n = nums.len();
    if n <= 1 {
      return 0;
    }

    let mut val: Vec<i64> = nums.iter().map(|&x| x as i64).collect();
    let mut prv: Vec<i64> = (0..n as i64).map(|i| i - 1).collect(); // prev idx (-1 = none)
    let mut nxt: Vec<i64> = (0..n as i64).map(|i| i + 1).collect(); // next idx (n = none)
    let mut removed = vec![false; n];

    // heap: Reverse((sum, left_idx))
    let mut heap: BinaryHeap<Reverse<(i64, usize)>> = BinaryHeap::new();
    let mut bad_count = 0i32;

    for i in 0..n - 1 {
      heap.push(Reverse((val[i] + val[i + 1], i)));
      if val[i] > val[i + 1] {
        bad_count += 1;
      }
    }

    let mut ops = 0i32;

    while bad_count > 0 {
      // Find valid minimum-sum pair (lazy deletion)
      let (i, j) = loop {
        let Reverse((sum, i)) = match heap.peek() {
          Some(&x) => x,
          None => break (0, 0), // shouldn't happen
        };
        if removed[i] {
          heap.pop();
          continue;
        }
        let j = nxt[i] as usize;
        if j >= n || removed[j] {
          heap.pop();
          continue;
        }
        if val[i] + val[j] != sum {
          heap.pop();
          continue;
        }
        heap.pop();
        break (i, j);
      };

      // Update bad_count for pairs being removed
      let pi = prv[i];
      let nj = nxt[j];

      if pi >= 0 {
        let pi = pi as usize;
        if val[pi] > val[i] {
          bad_count -= 1;
        }
      }
      if val[i] > val[j] {
        bad_count -= 1;
      }
      if nj < n as i64 {
        let nj = nj as usize;
        if val[j] > val[nj] {
          bad_count -= 1;
        }
      }

      // Merge j into i
      val[i] = val[i] + val[j];
      removed[j] = true;
      nxt[i] = nxt[j];
      if nj < n as i64 {
        prv[nj as usize] = i as i64;
      }

      // Add new pairs to bad_count and heap
      if pi >= 0 {
        let pi = pi as usize;
        if val[pi] > val[i] {
          bad_count += 1;
        }
        heap.push(Reverse((val[pi] + val[i], pi)));
      }
      if nxt[i] < n as i64 {
        let ni = nxt[i] as usize;
        if val[i] > val[ni] {
          bad_count += 1;
        }
        heap.push(Reverse((val[i] + val[ni], i)));
      }

      ops += 1;
    }

    ops
  }
}