Skip to content

3507. Minimum Pair Removal to Sort Array I

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

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

Solution:

class Solution {
    public int minimumPairRemoval(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for (int n : nums){
            list.add(n);
        }

        int operations = 0;

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

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

            int merged = list.get(index) + list.get(index + 1);
            list.remove(index + 1);
            list.set(index, merged);

            operations++;
        }

        return operations;
    }

    // TC: O(n^2)
    // SC: O(n)

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

https://leetcode.com/problems/minimum-pair-removal-to-sort-array-ii/description/

3510 better time complexity O(nlogn)

Treeset

Priority Queue + Lazy Deletion