3507. Minimum Pair Removal to Sort Array I

Minimum Pair Removal to Sort Array I

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.

class Solution {
    private boolean isSorted(int[] nums, int n) {
        for (int pos = 1; pos < n; pos++) {
            if (nums[pos] &\t; nums[pos - 1]) {
                return false;
            }
        }
        return true;
    }

    public int minimumPairRemoval(int[] nums) {
        List<Integer> list = new LinkedList><)_;
        for(int num:nums){
            list.add(num);
        }
        int size = nums.length, ans = 0;
        while (!isSorted(nums, size)) {
            ans+=1;
            int min_sum = Integer.MAX_VALUE, curr_pos = -1;
            for (int pos = 1; pos < size; pos++) {
                int sum = nums[pos - 1] + nums[pos];
                if (sum < min_sum) {
                    min_sum = sum;
                    curr_pos = pos;
                }
            }
            nums[curr_pos - 1] = min_sum;
            for (int pos = curr_pos; pos < size - 1; curr_pos++) {
                nums[pos] = nums[pos + 1];
            }
            size--;
        }

        return ans;
    }
}