🎡Beginner-Friendly Guide 'Minimum Pair Removal to Sort Array I' - Problem 3507 (C++, Python, JavaScript)

Sorting an array usually involves swapping elements, but what if you had to combine them instead? This problem challenges you to transform an unsorted list into a sorted one by merging adjacent neighbors based on their sums. It is a fantastic exercise in greedy simulation and array manipulation.

You're given:

• An array of integers called nums.
• A specific operation: select the adjacent pair with the minimum sum. If there is a tie, pick the leftmost one.
• The action: replace that pair with their sum, effectively reducing the array size by 1.

Your goal:

• Find the minimum number of operations required to make the array non-decreasing, meaning every element must be less than or equal to the one following it.

---

Intuition: The Greedy Simulation

The problem provides a very specific "greedy" rule: always pick the smallest sum first. Because the constraints are small (), we can directly simulate this process.

1. Check Status: First, we look at the array to see if it is already sorted. If nums[i] <= nums[i+1] for all elements, we are finished.
2. Find the Target: If it is not sorted, we scan the array from left to right to find which two neighbors, when added together, produce the smallest result.
3. Merge: We replace the first element of that pair with the sum and remove the second element from the list.
4. Repeat: We count this as one operation and repeat the check until the array satisfies the non-decreasing condition.

---

Walkthrough: Understanding the Examples

Example 1: nums = [5, 2, 3, 1]

1. Check: The array is not sorted because .
2. Scan for Min Sum:
3. (5, 2) sum = 7
4. (2, 3) sum = 5

5. (3, 1) sum = 4 (This is the minimum)

6. Operation 1: Replace (3, 1) with 4. Array becomes [5, 2, 4].

7. Check: Still not sorted because .

8. Scan for Min Sum:

9. (5, 2) sum = 7

10. (2, 4) sum = 6 (This is the minimum)

11. Operation 2: Replace (2, 4) with 6. Array becomes [5, 6].

12. Check: Sorted! Total operations: 2.

---

C++ Solution

class Solution {
public:
    // Helper function to check if the array is not sorted
    bool isNotSorted(const vector<int>& nums) {
        for (int i = 0; i + 1 < (int)nums.size(); i++) {
            if (nums[i] > nums[i + 1]) return true;
        }
        return false;
    }

    int minimumPairRemoval(vector<int>& nums) {
        int operations = 0;
        // Continue operating while the array is unsorted
        while (isNotSorted(nums)) {
            int idx = 0;
            int minSum = nums[0] + nums[1];

            // Find the leftmost pair with the minimum sum
            for (int i = 1; i + 1 < (int)nums.size(); i++) {
                int currentSum = nums[i] + nums[i + 1];
                if (currentSum < minSum) {
                    minSum = currentSum;
                    idx = i;
                }
            }

            // Replace the pair with their sum
            nums[idx] = nums[idx] + nums[idx + 1];
            // Remove the second element of the pair
            nums.erase(nums.begin() + (idx + 1));

            operations++;
        }

        return operations;
    }
};

Python Solution

class Solution:
    def minimumPairRemoval(self, nums: List[int]) -> int:
        def is_not_sorted(arr):
            for i in range(len(arr) - 1):
                if arr[i] > arr[i + 1]:
                    return True
            return False

        operations = 0
        while is_not_sorted(nums):
            idx = 0
            min_sum = nums[0] + nums[1]

            # Find the leftmost pair with the minimum sum
            for i in range(1, len(nums) - 1):
                current_sum = nums[i] + nums[i + 1]
                if current_sum < min_sum:
                    min_sum = current_sum
                    idx = i

            # Merge the pair
            nums[idx] = nums[idx] + nums[idx + 1]
            nums.pop(idx + 1)

            operations += 1

        return operations

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumPairRemoval = function(nums) {
    const isNotSorted = (arr) => {
        for (let i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) return true;
        }
        return false;
    };

    let operations = 0;
    while (isNotSorted(nums)) {
        let idx = 0;
        let minSum = nums[0] + nums[1];

        // Find the leftmost pair with the minimum sum
        for (let i = 1; i < nums.length - 1; i++) {
            let currentSum = nums[i] + nums[i + 1];
            if (currentSum < minSum) {
                minSum = currentSum;
                idx = i;
            }
        }

        // Merge the pair
        nums[idx] = nums[idx] + nums[idx + 1];
        nums.splice(idx + 1, 1);

        operations++;
    }

    return operations;
};

---

Key Takeaways

• Greedy Simulation: Sometimes the best way to solve a problem is to follow the instructions literally step by step.
• Array Mutation: Learning how to remove elements (erase, pop, or splice) while iterating is a fundamental skill across all languages.
• Loop Termination: Using a helper function like isNotSorted makes the logic of the while loop much cleaner and easier to debug.

Final Thoughts

This problem mimics real world data consolidation tasks. In systems like log processing or financial ledger reconciliation, you often have to merge smaller entries into larger ones to satisfy specific constraints or simplify reports. While this specific simulation has a complexity of approximately , it is perfectly efficient for the small constraints of this problem and prepares you for more advanced "Merge" style problems in technical interviews.