Minimum Pair Removal to Sort Array II

Problem

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).

Examples

Example 1

Input: nums = [5,2,3,1]
Output: 2
Explanation:
* The pair `(3,1)` has the minimum sum of 4. After replacement, `nums = [5,2,4]`.
* The pair `(2,4)` has the minimum sum of 6. After replacement, `nums = [5,6]`.
The array `nums` became non-decreasing in two operations.

Example 2

Input: nums = [1,2,2]
Output: 0
Explanation:
The array `nums` is already sorted.

Constraints

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

Solution

Method 1 – Simulation with Priority Queue (Heap)

Intuition

We need to repeatedly merge the adjacent pair with the minimum sum, always choosing the leftmost if there are ties. This is a simulation problem best solved with a min-heap and a doubly-linked list or array to track pairs and their positions efficiently.

Approach

1. Build a list of pairs (sum, index) for all adjacent pairs.
2. Use a min-heap to always pick the leftmost minimum sum pair.
3. When merging, update the neighbors and push new pairs into the heap.
4. Continue until the array is non-decreasing.

Code

C++

#include <vector>
#include <queue>
class Solution {
public:
    int minPairRemoval(std::vector<int>& nums) {
        int n = nums.size(), ops = 0;
        if (n <= 1) return 0;
        std::vector<int> arr(nums);
        while (true) {
            bool sorted = true;
            for (int i = 1; i < arr.size(); ++i) {
                if (arr[i] < arr[i-1]) { sorted = false; break; }
            }
            if (sorted) break;
            int minSum = arr[0]+arr[1], idx = 0;
            for (int i = 1; i < arr.size()-1; ++i) {
                if (arr[i]+arr[i+1] < minSum) {
                    minSum = arr[i]+arr[i+1];
                    idx = i;
                }
            }
            arr[idx] = arr[idx]+arr[idx+1];
            arr.erase(arr.begin()+idx+1);
            ++ops;
        }
        return ops;
    }
};

Go

func minPairRemoval(nums []int) int {
    arr := make([]int, len(nums))
    copy(arr, nums)
    ops := 0
    for {
        sorted := true
        for i := 1; i < len(arr); i++ {
            if arr[i] < arr[i-1] { sorted = false; break }
        }
        if sorted { break }
        minSum, idx := arr[0]+arr[1], 0
        for i := 1; i < len(arr)-1; i++ {
            if arr[i]+arr[i+1] < minSum {
                minSum = arr[i]+arr[i+1]
                idx = i
            }
        }
        arr[idx] = arr[idx]+arr[idx+1]
        arr = append(arr[:idx+1], arr[idx+2:]...)
        ops++
    }
    return ops
}

Java

import java.util.*;
class Solution {
    public int minPairRemoval(int[] nums) {
        List<Integer> arr = new ArrayList<>();
        for (int x : nums) arr.add(x);
        int ops = 0;
        while (true) {
            boolean sorted = true;
            for (int i = 1; i < arr.size(); ++i) {
                if (arr.get(i) < arr.get(i-1)) { sorted = false; break; }
            }
            if (sorted) break;
            int minSum = arr.get(0)+arr.get(1), idx = 0;
            for (int i = 1; i < arr.size()-1; ++i) {
                if (arr.get(i)+arr.get(i+1) < minSum) {
                    minSum = arr.get(i)+arr.get(i+1);
                    idx = i;
                }
            }
            arr.set(idx, arr.get(idx)+arr.get(idx+1));
            arr.remove(idx+1);
            ops++;
        }
        return ops;
    }
}

Kotlin

class Solution {
    fun minPairRemoval(nums: IntArray): Int {
        val arr = nums.toMutableList()
        var ops = 0
        while (true) {
            if ((1 until arr.size).all { arr[it] >= arr[it-1] }) break
            var minSum = arr[0]+arr[1]
            var idx = 0
            for (i in 1 until arr.size-1) {
                if (arr[i]+arr[i+1] < minSum) {
                    minSum = arr[i]+arr[i+1]
                    idx = i
                }
            }
            arr[idx] = arr[idx]+arr[idx+1]
            arr.removeAt(idx+1)
            ops++
        }
        return ops
    }
}

Python

class Solution:
    def minPairRemoval(self, nums: list[int]) -> int:
        arr = nums[:]
        ops = 0
        while True:
            if all(arr[i] >= arr[i-1] for i in range(1, len(arr))): break
            min_sum, idx = arr[0]+arr[1], 0
            for i in range(1, len(arr)-1):
                if arr[i]+arr[i+1] < min_sum:
                    min_sum, idx = arr[i]+arr[i+1], i
            arr[idx] = arr[idx]+arr[idx+1]
            arr.pop(idx+1)
            ops += 1
        return ops

Rust

impl Solution {
    pub fn min_pair_removal(nums: Vec<i32>) -> i32 {
        let mut arr = nums.clone();
        let mut ops = 0;
        while arr.windows(2).any(|w| w[1] < w[0]) {
            let (mut min_sum, mut idx) = (arr[0]+arr[1], 0);
            for i in 1..arr.len()-1 {
                if arr[i]+arr[i+1] < min_sum {
                    min_sum = arr[i]+arr[i+1];
                    idx = i;
                }
            }
            arr[idx] = arr[idx]+arr[idx+1];
            arr.remove(idx+1);
            ops += 1;
        }
        ops
    }
}

TypeScript

class Solution {
    minPairRemoval(nums: number[]): number {
        let arr = nums.slice();
        let ops = 0;
        while (true) {
            if (arr.every((v,i)=>i==0||v>=arr[i-1])) break;
            let minSum = arr[0]+arr[1], idx = 0;
            for (let i = 1; i < arr.length-1; ++i) {
                if (arr[i]+arr[i+1] < minSum) {
                    minSum = arr[i]+arr[i+1];
                    idx = i;
                }
            }
            arr[idx] = arr[idx]+arr[idx+1];
            arr.splice(idx+1,1);
            ops++;
        }
        return ops;
    }
}

Complexity

• ⏰ Time complexity: O(n^2) worst case (each operation scans the array).
• 🧺 Space complexity: O(n) (copy of array).