3507. Minimum Pair Removal to Sort Array I

/**
 * Problem: LeetCode 3507 - Minimum Pair Removal to Sort Array I
 * Difficulty: Easy
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.ArrayList;
import java.util.List;

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

        int ops = 0;
        while (!isNonDecreasing(list)) {
            int minSum = Integer.MAX_VALUE;
            int minIdx = -1;

            // Find the leftmost adjacent pair with the minimum sum
            for (int i = 0; i < list.size() - 1; i++) {
                int sum = list.get(i) + list.get(i + 1);
                if (sum < minSum) {
                    minSum = sum;
                    minIdx = i;
                }
            }

            // Replace the pair with their sum
            list.set(minIdx, minSum);
            list.remove(minIdx + 1);
            ops++;
        }

        return ops;
    }

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

"""
Problem: LeetCode 3507 - Minimum Pair Removal to Sort Array I
Difficulty: Easy
Language: Python
Author: CodeByTushu
"""
from typing import List

class Solution:
    def minimumPairRemoval(self, nums: List[int]) -> int:
        arr = list(nums)
        ops = 0

        while not self._is_non_decreasing(arr):
            min_sum = float('inf')
            min_idx = -1

            # Find leftmost adjacent pair with minimum sum
            for i in range(len(arr) - 1):
                pair_sum = arr[i] + arr[i + 1]
                if pair_sum < min_sum:
                    min_sum = pair_sum
                    min_idx = i

            # Replace the pair with their sum
            arr[min_idx] = min_sum
            arr.pop(min_idx + 1)
            ops += 1

        return ops

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

/**
 * Problem: LeetCode 3507 - Minimum Pair Removal to Sort Array I
 * Difficulty: Easy
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <climits>

using namespace std;

class Solution {
public:
    int minimumPairRemoval(vector<int>& nums) {
        vector<int> arr = nums;
        int ops = 0;

        while (!isNonDecreasing(arr)) {
            int minSum = INT_MAX;
            int minIdx = -1;

            // Find leftmost adjacent pair with minimum sum
            for (size_t i = 0; i + 1 < arr.size(); ++i) {
                int sum = arr[i] + arr[i + 1];
                if (sum < minSum) {
                    minSum = sum;
                    minIdx = i;
                }
            }

            // Replace the pair with their sum
            arr[minIdx] = minSum;
            arr.erase(arr.begin() + minIdx + 1);
            ops++;
        }

        return ops;
    }

private:
    bool isNonDecreasing(const vector<int>& arr) {
        for (size_t i = 0; i + 1 < arr.size(); ++i) {
            if (arr[i] > arr[i + 1]) {
                return false;
            }
        }
        return true;
    }
};

/**
 * Problem: LeetCode 3507 - Minimum Pair Removal to Sort Array I
 * Difficulty: Easy
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumPairRemoval = function(nums) {
    const arr = [...nums];
    let ops = 0;

    const isNonDecreasing = (a) => {
        for (let i = 0; i < a.length - 1; i++) {
            if (a[i] > a[i + 1]) return false;
        }
        return true;
    };

    while (!isNonDecreasing(arr)) {
        let minSum = Infinity;
        let minIdx = -1;

        // Find leftmost adjacent pair with minimum sum
        for (let i = 0; i < arr.length - 1; i++) {
            const sum = arr[i] + arr[i + 1];
            if (sum < minSum) {
                minSum = sum;
                minIdx = i;
            }
        }

        // Replace pair with sum
        arr.splice(minIdx, 2, minSum);
        ops++;
    }

    return ops;
};