🔥 Leetcode 3507: Minimum Pair Removal to Sort Array I
💡IntuitionWe keep merging the pair with the smallest sum until the array becomes non-decreasing.
Each merge helps fix the order.
We count how many merges are ne
# 💡Intuition
We keep merging the pair with the smallest sum until the array becomes non-decreasing.
Each merge helps fix the order.
We count how many merges are needed.

## 🔍 Approach  
- Check if the array is already sorted.  
- If not sorted:  
  - Find the **leftmost pair** with the **smallest sum**.  
  - Replace the pair with their **sum**.  
    - Put the sum in the first position.  
    - Remove the second number.  
- Repeat the above steps.  
- Count how many times we do this until the array is sorted.

---

## ⏱️ Complexity  
- **Time Complexity:** `O(n^2)`  
  We check and modify the array many times as it gets smaller.
  
- **Space Complexity:** `O(1)`  
  No extra space is used except for simple variables.

---


# Code
```cpp []
class Solution {

private:
    void shiftLeft(vector<int>& nums, int index) {
        for (int i = index; i < nums.size() - 1; i++) {
            nums[i] = nums[i + 1];
        }
        nums.pop_back();
    }
    void mergeMinPair(vector<int>& nums) {
        //search for min Sum
        int minSum = INT_MAX;
        int minIndx = 0;
        for (int i = 0; i < nums.size()-1; i++) {
            int sum = nums[i] + nums[i + 1];
            if (sum < minSum) {
                minIndx = i;
                minSum = sum;
            }
        }
        nums[minIndx] = minSum;
        shiftLeft(nums, minIndx + 1);
    }
    bool isSorted(vector<int>&nums){
        for(int i=0;i<nums.size()-1;i++){
            if(nums[i]>nums[i+1])return false;
        }
        return true;
    }

public:
    int minimumPairRemoval(vector<int>& nums) {
        int cnt = 0;
        while (!isSorted(nums)) {
            mergeMinPair(nums);
            cnt++;
        }
        return cnt;
    }
};
```
['Greedy', 'C++']