3507. Minimum Pair Removal to Sort Array I

Array
Simulation
Greedy

TIME

O(n³)

SPACE

O(1)

Intuition

Simulate the process: repeatedly find the adjacent pair with minimum sum, merge them, and count operations until the array is non-decreasing.

Solution

Check if sorted: If array is already non-decreasing, return 0.
Find minimum sum pair: Scan all adjacent pairs, find the one with minimum sum (leftmost if tie).
Merge pair: Replace the two elements with their sum, reducing array size by 1.
Repeat: Continue until array is non-decreasing.
Count operations: Return the number of merge operations performed.

Complexity

Time: O(n³), each operation is O(n) to find min pair + O(n) to check sorted, up to O(n) operations
Space: O(1), in-place modifications (or O(n) if using list copy)

Edge Cases

Already sorted → return 0
Single element → return 0 (trivially sorted)
All elements equal → return 0
Descending array → may need multiple merges

Code

from typing import List


class Solution:
    def minimumPairRemoval(self, nums: List[int]) -> int:
        """
        3507. Minimum Pair Removal to Sort Array I
        Time: O(n³)
        Space: O(1)
        """
        ops = 0

        def is_non_decreasing(arr: List[int]) -> bool:
            for i in range(1, len(arr)):
                if arr[i] < arr[i - 1]:
                    return False
            return True

        while not is_non_decreasing(nums):
            min_sum = float('inf')
            idx = 0

            for i in range(len(nums) - 1):
                s = nums[i] + nums[i + 1]
                if s < min_sum:
                    min_sum = s
                    idx = i

            nums[idx] = nums[idx] + nums[idx + 1]
            nums.pop(idx + 1)
            ops += 1

        return ops

import java.util.ArrayList;
import java.util.List;

/**
 * 3507. Minimum Pair Removal to Sort Array I
 * Time: O(n³)
 * Space: O(n)
 */
class Solution {
    public int minimumPairRemoval(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            list.add(num);
        }

        int ops = 0;

        while (!isNonDecreasing(list)) {
            int minSum = Integer.MAX_VALUE;
            int idx = 0;

            for (int i = 0; i < list.size() - 1; i++) {
                int sum = list.get(i) + list.get(i + 1);
                if (sum < minSum) {
                    minSum = sum;
                    idx = i;
                }
            }

            list.set(idx, list.get(idx) + list.get(idx + 1));
            list.remove(idx + 1);
            ops++;
        }

        return ops;
    }

    private boolean isNonDecreasing(List<Integer> arr) {
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i) < arr.get(i - 1)) {
                return false;
            }
        }
        return true;
    }
}