Minimum Pair Removal to Sort Array I

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 <= 50
-1000 <= nums[i] <= 1000

Solution

Method 1 – Simulation (Brute Force)

Intuition

Since the array is small (n ≤ 50), we can simulate the process directly: repeatedly merge the leftmost adjacent pair with the minimum sum until the array is non-decreasing.

Approach

While the array is not non-decreasing:
Find the leftmost adjacent pair with the minimum sum.
Merge the pair (replace with their sum).
Count the number of operations.

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


#include <vector>
class Solution {
public:
    int minPairRemoval(std::vector<int>& nums) {
        std::vector<int> arr(nums);
        int ops = 0;
        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
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


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


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
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 (Brute Force)#

Intuition#

Approach#

Code#

Complexity#