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

1
2
3
4
5
6


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

1
2
3
4


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

Constraints

1 <= nums.length <= 10^5
-109 <= 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

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

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


#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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


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

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Simulation with Priority Queue (Heap)#

Intuition#

Approach#

Code#

Complexity#