# Minimum Pair Removal to Sort Array II
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-pair-removal-to-sort-array-ii)
Canonical: https://scaleengineer.com/dsa/problems/minimum-pair-removal-to-sort-array-ii
**Data structures:** Array, Hash Table, Linked List, Heap (Priority Queue), Doubly-Linked List, Ordered Set
---
## Problem
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.

**Constraints:**

* `1 <= nums.length <= 105`
* `-109 <= nums[i] <= 109`

# Approaches
## Brute-Force Simulation
This approach directly simulates the process described in the problem. It uses a dynamic list, such as `java.util.ArrayList`, to represent the array `nums`. In each step of the simulation, it performs a linear scan through the list to find the adjacent pair with the minimum sum. After finding this pair, it merges them into a single element and increments the operation count. This process is repeated until the entire list becomes non-decreasing.
**Time:** O(K * N), where N is the initial length of the array and K is the number of operations. Each operation involves scanning the list to check for sortedness (O(N)), finding the minimum sum pair (O(N)), and updating the list (O(N) for an ArrayList). Since K can be up to N-1, the worst-case time complexity is O(N^2). · **Space:** O(N), where N is the number of elements in the input array. This space is used to store the list of numbers.
**Pros:** Simple to understand and implement.; Directly follows the logic described in the problem statement.
**Cons:** Highly inefficient for large inputs due to its quadratic time complexity.; Will likely result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.
### Explanation
The brute-force simulation is the most straightforward way to solve the problem. We use a `List<Long>` to store the numbers, which allows for dynamic resizing and prevents integer overflow when summing up large numbers.

The simulation proceeds in a loop. In each iteration, we first need to determine if we should stop. This is done by a helper function `isSorted`, which traverses the list to check if `list[i] >= list[i-1]` for all `i`. If the list is sorted, we exit the loop.

If the list is not yet sorted, we proceed with one operation. We iterate through all adjacent pairs from the beginning of the list, calculating their sum and keeping track of the minimum sum found so far, along with the index of that pair. The problem specifies that if there's a tie in sums, the leftmost pair should be chosen, which is naturally handled by a simple linear scan from left to right.

After finding the pair `(list[minIndex], list[minIndex+1])` with the minimum sum, we replace them with their sum. In an `ArrayList`, this involves updating the value at `minIndex` and removing the element at `minIndex+1`. Each such merge constitutes one operation, so we increment our counter.

This cycle of checking, finding the minimum, and merging continues until the list is non-decreasing.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int minOperations(int[] nums) {
        if (nums.length <= 1) {
            return 0;
        }

        List<Long> currentNums = new ArrayList<>();
        for (int num : nums) {
            currentNums.add((long) num);
        }

        int operations = 0;
        while (true) {
            if (isSorted(currentNums)) {
                break;
            }

            long minSum = Long.MAX_VALUE;
            int minIndex = -1;

            for (int i = 0; i < currentNums.size() - 1; i++) {
                long currentSum = currentNums.get(i) + currentNums.get(i + 1);
                if (currentSum < minSum) {
                    minSum = currentSum;
                    minIndex = i;
                }
            }

            long val1 = currentNums.get(minIndex);
            long val2 = currentNums.get(minIndex + 1);
            currentNums.set(minIndex, val1 + val2);
            currentNums.remove(minIndex + 1);
            operations++;
        }

        return operations;
    }

    private boolean isSorted(List<Long> nums) {
        for (int i = 1; i < nums.size(); i++) {
            if (nums.get(i) < nums.get(i - 1)) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- 1. Initialize `operations = 0` and convert the input array `nums` into a `java.util.List<Long>` to handle large numbers and potential overflows.
- 2. Start an infinite loop that will be broken once the list is sorted.
- 3. Inside the loop, first check if the current list is sorted in non-decreasing order. If it is, break the loop.
- 4. If not sorted, iterate through all adjacent pairs in the list to find the one with the minimum sum. Keep track of this minimum sum and the index of the first element of the pair (`minIndex`).
- 5. Perform the merge operation: calculate the sum of the elements at `minIndex` and `minIndex + 1`. Update the element at `minIndex` with this sum and remove the element at `minIndex + 1`.
- 6. Increment the `operations` counter.
- 7. Once the loop terminates, return the total `operations` count.

## Optimized Simulation with Doubly Linked List and Priority Queue
This approach optimizes the simulation by using more efficient data structures to handle the main operations. A doubly linked list is used to represent the array, which allows for O(1) element removal and neighbor access. A min-priority queue is employed to find the minimum sum pair efficiently in O(log N) time. The termination condition (checking if the array is sorted) is also optimized by maintaining a real-time count of inversions (adjacent elements `a, b` where `a > b`). The simulation stops when this count drops to zero.
**Time:** O(K * log N), where N is the initial length of the array and K is the number of operations. The main loop runs K times. Each iteration involves at least one O(log N) poll from the priority queue and potentially two O(log N) additions. The number of stale entries polled does not change the overall asymptotic complexity. In the worst case, K is O(N), leading to a total time complexity of O(N log N). · **Space:** O(N), where N is the initial number of elements. This space is required for the doubly linked list (O(N)), the priority queue (can contain O(N) pairs), and the auxiliary `removed` array (O(N)).
**Pros:** Highly efficient, with a time complexity suitable for large inputs.; Optimizes the key bottlenecks of the simulation by using appropriate data structures.; The inversion counting method avoids costly checks for sortedness in each iteration.
**Cons:** Significantly more complex to implement than the brute-force approach.; Requires careful management of data structures, pointers, and state (especially for staleness checks and inversion counting).
### Explanation
To overcome the O(N^2) complexity of the naive simulation, we need to speed up two key steps: finding the minimum sum pair and checking for the sorted condition.

- **Finding Minimum Sum Pair:** A min-priority queue (min-heap) is perfect for this. We store objects representing each adjacent pair's sum and a reference to the pair's first node. This lets us retrieve the minimum sum pair in O(log N) time.

- **Efficient Merging:** An `ArrayList` is slow for removals in the middle. A doubly linked list (DLL) is ideal here. Each number is a node in the DLL. Merging a pair `(u, v)` involves updating `u.val`, changing `u.next` to point to `v.next`, and updating the back-pointer of `v.next`. This is an O(1) operation.

- **Checking Sorted Condition:** Linearly scanning the list in each step is too slow. Instead, we can maintain a counter for the number of `inversions` (places where `node.val > node.next.val`). We initialize this count once. After each merge, we only need to check the newly formed adjacent pairs to update the inversion count in O(1) time. The simulation runs until `inversions` becomes 0.

- **Handling Stale Data:** When we merge a pair, the pairs involving its neighbors become invalid. Instead of trying to find and remove these from the priority queue (which is inefficient), we simply add the new pairs. When we extract a pair from the PQ, we perform a *staleness check*. A pair is stale if one of its nodes has been removed or if the sum of the current values of its nodes doesn't match the sum stored in the PQ. We discard stale pairs and process the next one.

```java
import java.util.PriorityQueue;

class Solution {
    static class Node {
        long val;
        Node prev, next;
        int id; // Unique identifier for the node, e.g., original index
        Node(long val, int id) {
            this.val = val;
            this.id = id;
        }
    }

    static class Pair implements Comparable<Pair> {
        long sum;
        Node node; // The first node of the pair
        
        Pair(long sum, Node node) {
            this.sum = sum;
            this.node = node;
        }

        @Override
        public int compareTo(Pair other) {
            if (this.sum != other.sum) {
                return Long.compare(this.sum, other.sum);
            }
            // Tie-breaking: choose the leftmost pair
            return Integer.compare(this.node.id, other.node.id);
        }
    }

    public int minOperations(int[] nums) {
        if (nums.length <= 1) return 0;

        Node head = new Node(0, -1);
        Node tail = new Node(0, nums.length);
        Node curr = head;
        
        int inversions = 0;
        Node[] nodes = new Node[nums.length];
        for (int i = 0; i < nums.length; i++) {
            nodes[i] = new Node(nums[i], i);
            curr.next = nodes[i];
            nodes[i].prev = curr;
            curr = nodes[i];
            if (i > 0 && nodes[i-1].val > nodes[i].val) {
                inversions++;
            }
        }
        curr.next = tail;
        tail.prev = curr;

        PriorityQueue<Pair> pq = new PriorityQueue<>();
        for (int i = 0; i < nums.length - 1; i++) {
            pq.add(new Pair(nodes[i].val + nodes[i+1].val, nodes[i]));
        }

        int operations = 0;
        boolean[] removed = new boolean[nums.length];

        while (inversions > 0 && !pq.isEmpty()) {
            Pair p = pq.poll();
            Node u = p.node;
            
            if (removed[u.id] || u.next == tail) continue;
            
            Node v = u.next;
            if (removed[v.id]) continue;

            // Stale pair check
            if (u.val + v.val != p.sum) continue;

            operations++;

            // Update inversions before merge
            if (u.prev != head && u.prev.val > u.val) inversions--;
            if (u.val > v.val) inversions--;
            if (v.next != tail && v.val > v.next.val) inversions--;

            // Perform merge
            u.val += v.val;
            removed[v.id] = true;
            u.next = v.next;
            v.next.prev = u;

            // Update inversions after merge
            if (u.prev != head && u.prev.val > u.val) inversions++;
            if (u.next != tail && u.val > u.next.val) inversions++;

            // Add new pairs to PQ
            if (u.prev != head) {
                pq.add(new Pair(u.prev.val + u.val, u.prev));
            }
            if (u.next != tail) {
                pq.add(new Pair(u.val + u.next.val, u));
            }
        }

        return operations;
    }
}
```
### Algorithm
- 1. **Initialization:**
  - Create a Doubly Linked List (DLL) from `nums`, where each node stores its value and a unique ID (its original index). Add sentinel head and tail nodes.
  - Create a Min-Priority Queue to store `Pair` objects. A `Pair` contains a `sum` and a reference to the first `Node` of the pair.
  - Populate the PQ with all initial adjacent pairs from the DLL.
  - Compute the initial number of `inversions` (where `node.val > node.next.val`).
- 2. **Simulation Loop:** Continue as long as `inversions > 0`.
  - a. Extract the `Pair` with the minimum sum from the PQ.
  - b. **Staleness Check:** Verify the extracted pair is still valid. A pair is stale if its nodes have been removed or if their values have changed such that their current sum doesn't match the sum stored in the `Pair`. If stale, discard and continue to the next pair in the PQ.
  - c. **Merge:** If the pair `(u, v)` is valid:
    - Increment `operations` count.
    - Update the `inversions` count: decrement for inversions removed by the merge, and increment for any new inversions created.
    - Update the DLL: set `u.val = u.val + v.val`, and bypass `v` by setting `u.next = v.next`. Mark `v` as removed.
    - Update the PQ: Add new pairs formed by the updated node `u` and its new neighbors (`u.prev`, `u.next`).
- 3. **Termination:** When the loop finishes (`inversions` is 0), return the total `operations`.