Beats 100% ✅. Detailed Code Walkthrough.
IntuitionThe idea is to repeatedly merge the adjacent pair that has the smallest sum. By always choosing the pair with the smallest sum, we expect the array to
# Intuition
The idea is to repeatedly merge the adjacent pair that has the smallest sum. By always choosing the pair with the smallest sum, we expect the array to gradually evolve into a non-decreasing order. Each merge reduces the array size by one and counts as one operation.


# Approach
1. **Check if Sorted:**
First, we check if the array is already non-decreasing. If it is, no operations are needed.

2. **Find Minimum Sum Pair:**
If not sorted, iterate over the array to locate the adjacent pair with the minimum sum. In case of a tie, choose the leftmost pair.

3. **Merge the Pair:**
Replace the left element of the pair with the sum of both elements and then remove the right element from the array.

4. **Repeat Until Sorted:**
Continue the process until the array becomes non-decreasing, while counting the number of operations.



# Complexity
- Time complexity:
In the worst-case scenario, for each merge operation, we scan the array (O(n)) and then perform an erase operation (O(n)). With at most O(n) merge operations, the ***total time complexity is O(n²)***.
>  **Given the small constraint (n ≤ 50), this is acceptable**.



- Space complexity:
The solution uses a constant amount of extra space aside from the input array **(O(1) extra space)**. The operations are performed in-place.


# Code
```cpp []
class Solution {
public:
    bool isSorted(const vector<int>& nums) {
        for (int i = 0; i < nums.size() - 1; i++) {
            if (nums[i] > nums[i + 1])
                return false;
        }
        return true;
    }

    int minimumPairRemoval(vector<int>& nums) {
        int operations = 0;
        
        while (!isSorted(nums) && nums.size() > 1) {
            int minSum = 1e9;
            int pos = -1;
            
            for (int i = 0; i < nums.size() - 1; i++) {
                int curSum = nums[i] + nums[i + 1];
                if (curSum < minSum) {
                    minSum = curSum;
                    pos = i;
                }
            }
            nums[pos] = nums[pos] + nums[pos + 1];
            
            nums.erase(nums.begin() + pos + 1);
            operations++;
        }
        
        return operations;
    }
};
```
# Code Walkthrough
###### **Initialization:**
- `operations` is set to 0. This variable will count the number of merge operations performed.
###### **While Loop Condition:**
The loop continues as long as:

- The array is not sorted (i.e., `!isSorted(nums)` returns `true`), and
- The array has more than 1 element (`nums.size() > 1`).

This ensures that we stop when the array becomes non-decreasing or has only one element left (which is trivially sorted).

###### **Finding the Adjacent Pair with Minimum Sum:**

- Two variables are initialized:
    - `minSum` is set to a large value (1e9, i.e., 10^9) ensuring that any adjacent sum will be smaller.
    - `pos` is set to -1 to store the left index of the selected pair.
- A for-loop iterates over the vector from index 0 to `nums.size() - 2` (since we look at the pair `[i]` and `[i+1]`).
- For each pair, it calculates `curSum = nums[i] + nums[i + 1]`.
- If `curSum` is less than the current `minSum`, it updates minSum and stores the current index `i` in `pos`.
    - This ensures that by the end of the loop, `pos` holds the index of the left element in the adjacent pair which has the minimum sum.
    - If there are multiple with the same sum, since we update only when a strictly smaller sum is found, the leftmost occurrence is chosen.

###### **Merging the Selected Pair:**
- After identifying the pair at indices pos and pos + 1, the code performs the merge:
    - `nums[pos] = nums[pos] + nums[pos + 1];`
            - This line replaces the left element with the sum of both.
    - `nums.erase(nums.begin() + pos + 1);`
        - This line removes the right element from the vector so that the size is reduced by one.
    - The `operations` counter is then incremented by 1 as one operation has been completed.

###### **Returning the Final Answer:**
Once the while loop completes (meaning the vector is sorted in non-decreasing order or no more operations can be performed), the function returns the number of operations needed.
['C++']