# Minimum Pair Removal to Sort Array I
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-pair-removal-to-sort-array-i)
Canonical: https://scaleengineer.com/dsa/problems/minimum-pair-removal-to-sort-array-i
**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 <= 50`
* `-1000 <= nums[i] <= 1000`

# Approaches
## Direct Simulation using a List
This approach directly simulates the process described in the problem statement. We use a dynamic list, like Java's `ArrayList`, to represent the array `nums`. In a loop, we repeatedly check if the array is sorted. If not, we find the adjacent pair with the minimum sum, merge them by replacing them with their sum, update the list, and increment our operation counter. We continue this process until the list becomes non-decreasing.
**Time:** O(N^2)
The main `while` loop runs at most `N-1` times. In each iteration, we perform three main actions: checking if the list is sorted (O(N)), finding the minimum sum pair (O(N)), and updating the `ArrayList` (O(N)). This results in a total time complexity of O(N * N) = O(N^2). · **Space:** O(N)
We use an auxiliary `List` to store the numbers. The size of this list is at most `N`, where `N` is the length of the input array.
**Pros:** Simple to understand and implement as it directly follows the problem description.; Sufficiently fast for the given constraints (`N <= 50`).; Requires minimal complex data structures.
**Cons:** Not the most asymptotically efficient solution available.; Repeatedly scans the entire list in each step, which can be inefficient for larger arrays.
### Explanation
The algorithm is a straightforward simulation. We start by converting the input array into a `List` to make element removal and insertion easier. We then enter a loop that continues until the list is sorted in non-decreasing order.

Inside the loop, we first have a helper function, `isNonDecreasing`, which iterates through the list to check if `list.get(i) <= list.get(i + 1)` for all valid `i`. If this condition holds for the entire list, it means the list is sorted, and we can terminate the simulation.

If the list is not sorted, we proceed to find the adjacent pair with the minimum sum. We iterate through all adjacent pairs, keeping track of the minimum sum found so far and the index of the first element of that pair. The problem specifies that in case of a tie in sums, the leftmost pair should be chosen, which our linear scan naturally handles.

Once the minimum sum pair is identified at `minIndex`, we perform the merge operation. We calculate the sum of the two elements, remove them from the list, and insert the sum back at `minIndex`. Each merge operation counts as one, so we increment an `operations` counter.

The loop then repeats with the modified, smaller list. The process is guaranteed to terminate because the list size decreases by one in each iteration.

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

class Solution {
    public int minimumOperations(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 (isNonDecreasing(currentNums)) {
                break;
            }

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

            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 sum = currentNums.get(minIndex) + currentNums.get(minIndex + 1);
            
            currentNums.remove(minIndex + 1);
            currentNums.remove(minIndex);
            
            currentNums.add(minIndex, sum);
            operations++;
        }

        return operations;
    }

    private boolean isNonDecreasing(List<Long> list) {
        for (int i = 0; i < list.size() - 1; i++) {
            if (list.get(i) > list.get(i + 1)) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- 1. Initialize `operations = 0`.
- 2. Create a `List<Long>` from the input `nums` array to handle potential overflows and allow dynamic resizing.
- 3. Loop indefinitely:
    - a. Check if the list is non-decreasing. If it is, `break` the loop.
    - b. Initialize `minSum` to a very large value and `minIndex` to -1.
    - c. Iterate through the list from `i = 0` to `size - 2` to find the index `minIndex` of the adjacent pair with the minimum sum.
    - d. Get the values at `minIndex` and `minIndex + 1`.
    - e. Remove the two elements at `minIndex + 1` and `minIndex` (in this order to avoid index shifting issues).
    - f. Insert their sum at `minIndex`.
    - g. Increment the `operations` counter.
- 4. Return the final `operations` count.

## Optimized Simulation with Priority Queue
This approach optimizes the process of finding the minimum sum pair at each step. Instead of scanning the list every time (an O(N) operation), we use a min-priority queue to maintain the sums of all adjacent pairs. This allows us to retrieve the minimum sum pair in O(log N) time. To efficiently handle the merging of pairs and the resulting changes in adjacency, we represent the array using a doubly linked list, which allows for O(1) removal of elements and updating of neighbor relationships.
**Time:** O(N log N)
Building the linked list is O(N). Initializing the priority queue with N-1 pairs takes O(N log N). The main loop runs up to N-1 times. Each iteration involves polling from the PQ (O(log N)), constant time work for linked list updates, and adding at most two new pairs to the PQ (O(log N)). The check for sortedness takes O(N), but the dominant cost comes from the N-1 merge operations, each taking O(log N). Total time is O(N log N). · **Space:** O(N)
The doubly linked list requires O(N) space for the nodes. The priority queue will also store up to O(N) pairs in the worst case. Thus, the total auxiliary space complexity is O(N).
**Pros:** Asymptotically faster with a time complexity of O(N log N).; More scalable for larger input sizes (beyond the current constraints).
**Cons:** Significantly more complex to implement correctly compared to the direct simulation.; The overhead from the priority queue and linked list might make it slower for very small `N`.; Prone to subtle implementation bugs, especially in handling stale pairs and updating data structures.
### Explanation
To improve the time complexity, we need to optimize the step of finding the minimum sum pair. A min-priority queue is the ideal data structure for this, as it can provide the minimum element in logarithmic time.

However, using a priority queue introduces a new challenge: when we merge a pair, the adjacencies in the array change. For example, if we merge `(a, b)` into `c`, the old pairs involving `a` and `b` (like `(x, a)` and `(b, y)`) become invalid, and new pairs `(x, c)` and `(c, y)` are formed. The priority queue must reflect these changes.

We can solve this by using a doubly linked list to represent the array. Each node in the list holds a number. The priority queue will store objects representing adjacent pairs of nodes, ordered by their sum.

When we extract the minimum pair from the queue, we must first verify it's not 'stale'. A pair is stale if one of its nodes has already been merged into another. We can check this by adding a flag to each node or by verifying that the two nodes are still adjacent in the linked list (`node1.next == node2`).

If the pair is valid, we merge them. This involves updating the value of the first node, and then updating the pointers of the surrounding nodes to bypass the second node, effectively removing it. We then add new pairs (formed by the merged node and its new neighbors) to the priority queue. We don't need to explicitly remove stale pairs from the queue; the staleness check upon extraction is sufficient.

This process continues until the array becomes sorted. The overall approach is much faster asymptotically but requires careful implementation.

A conceptual sketch of the data structures:
```java
// Node for the doubly linked list
class Node {
    long val;
    Node prev, next;
    boolean isMerged = false;
    Node(long val) { this.val = val; }
}

// Object to store in the Priority Queue
class Pair implements Comparable<Pair> {
    long sum;
    Node left, right;

    Pair(Node l, Node r) {
        this.left = l;
        this.right = r;
        this.sum = l.val + r.val;
    }

    @Override
    public int compareTo(Pair other) {
        if (this.sum != other.sum) {
            return Long.compare(this.sum, other.sum);
        }
        // Tie-breaking rule is not explicitly handled here but would be based on original index.
        // For this problem, the PQ's internal tie-breaking is usually sufficient.
        return 0; 
    }
}

// Main logic sketch
public int minimumOperationsWithPQ(int[] nums) {
    // 1. Build doubly linked list and initial priority queue.
    // 2. Loop until sorted, performing operations:
    //    a. Poll from PQ.
    //    b. Check for staleness (if (left.isMerged || right.isMerged || left.next != right) continue;)
    //    c. Merge nodes in the linked list.
    //    d. Mark right node as merged.
    //    e. Add new pairs involving the merged node to the PQ.
    //    f. Increment operations count.
    // 3. Return operations.
    return 0; // Placeholder for full implementation
}
```
### Algorithm
- 1. Create a doubly linked list from the `nums` array. Each node stores its value and pointers to its neighbors.
- 2. Create a min-priority queue to store `Pair` objects, where each `Pair` represents two adjacent nodes and their sum.
- 3. Populate the priority queue with pairs from the initial linked list.
- 4. Initialize `operations = 0`.
- 5. Loop until the list is sorted:
    - a. Extract the `Pair` with the minimum sum from the priority queue.
    - b. Check if the pair is stale (i.e., its nodes have been modified or are no longer adjacent). If so, discard it and continue to the next pair.
    - c. If the pair is valid, perform the merge: update the left node's value with the sum, and adjust pointers in the linked list to remove the right node.
    - d. Add new pairs formed by the merged node and its new neighbors to the priority queue.
    - e. Increment `operations`.
- 6. Return `operations`.