🧼 Beginner-Friendly Guide 'Minimum Pair Removal to Sort Array II' - LeetCode 3510 (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 non-decreasing one by repeatedly merging the "smallest" adjacent neighbors. It is a fantastic exercise in greedy strategy and efficient data structure management.

---

Problem Summary

You're given:
An array of integers called nums.

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.

Your goal:
Find the minimum number of operations to make the array non-decreasing (sorted). In each operation, you must pick the adjacent pair with the minimum sum (choosing the leftmost if there is a tie) and replace them with their sum.

---

Intuition

The core of this problem is a Greedy Strategy. We are forced to pick the smallest sum first. Because the array can be quite large ( elements), we cannot simply search the array for the minimum sum every time, as that would be too slow.

To solve this efficiently, we use a Priority Queue (Min-Heap) to keep track of all adjacent sums. However, when we merge two numbers, the neighbors of those numbers change.

Instead of deleting items from the middle of an array (which is slow), we use a Doubly Linked List (simulated with prev and next arrays) to keep track of neighbors. When we merge two elements:

1. We update the value of the left element to be the new sum.
2. We "remove" the right element by skipping over it in our linked list.
3. We check if the new local relationships (with the left and right neighbors) have fixed or created any "unsorted" spots.
4. We add the new possible sums created by this merger into the Priority Queue.

---

Walkthrough: Understanding the Examples

Let's look at Example 1: nums = [5, 2, 3, 1]

1. Initial State: Pairs are (5,2) sum 7, (2,3) sum 5, (3,1) sum 4.
2. Step 1: The minimum sum is 4 from the pair (3,1). We merge them.
3. New array: [5, 2, 4].

4. One operation performed. The array is not sorted because 5 > 2.

5. Step 2: The pairs are (5,2) sum 7, (2,4) sum 6. The minimum sum is 6 from (2,4). We merge them.

6. New array: [5, 6].

7. Two operations performed. The array is now sorted!

---

Code Blocks

C++

#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    int minimumPairRemoval(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return 0;

        vector<long long> vals(nums.begin(), nums.end());
        vector<int> nexts(n), prevs(n);
        vector<bool> removed(n, false);

        // Min-heap to store {sum, left_index}
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

        int unsorted_cnt = 0;
        for (int i = 0; i < n; ++i) {
            prevs[i] = i - 1;
            nexts[i] = (i == n - 1) ? -1 : i + 1;
            if (i < n - 1) {
                if (vals[i] > vals[i + 1]) unsorted_cnt++;
                pq.push({vals[i] + vals[i + 1], i});
            }
        }

        if (unsorted_cnt == 0) return 0;

        int moves = 0;
        while (unsorted_cnt > 0 && !pq.empty()) {
            auto [sum, u] = pq.top();
            pq.pop();

            if (removed[u]) continue;
            int v = nexts[u];
            if (v == -1 || removed[v] || vals[u] + vals[v] != sum) continue;

            int p = prevs[u];
            int next_v = nexts[v];

            moves++;

            // Remove old unsorted counts
            if (p != -1 && vals[p] > vals[u]) unsorted_cnt--;
            if (vals[u] > vals[v]) unsorted_cnt--;
            if (next_v != -1 && vals[v] > vals[next_v]) unsorted_cnt--;

            // Perform Merge
            vals[u] = sum;
            nexts[u] = next_v;
            if (next_v != -1) prevs[next_v] = u;
            removed[v] = true;

            // Add new unsorted counts
            if (p != -1 && vals[p] > vals[u]) unsorted_cnt++;
            if (next_v != -1 && vals[u] > vals[next_v]) unsorted_cnt++;

            if (unsorted_cnt == 0) break;

            // Push new potential pairs
            if (p != -1) pq.push({vals[p] + vals[u], p});
            if (next_v != -1) pq.push({vals[u] + vals[next_v], u});
        }

        return moves;
    }
};

Python

import heapq

class Solution:
    def minimumPairRemoval(self, nums: list[int]) -> int:
        n = len(nums)
        if n <= 1: return 0

        vals = [float(x) for x in nums]
        nexts = [i + 1 for i in range(n)]
        prevs = [i - 1 for i in range(n)]
        nexts[n-1] = -1
        removed = [False] * n

        pq = []
        unsorted_cnt = 0

        for i in range(n - 1):
            if vals[i] > vals[i+1]:
                unsorted_cnt += 1
            heapq.heappush(pq, (vals[i] + vals[i+1], i))

        if unsorted_cnt == 0: return 0

        moves = 0
        while unsorted_cnt > 0 and pq:
            s, u = heapq.heappop(pq)

            if removed[u]: continue
            v = nexts[u]
            if v == -1 or removed[v] or vals[u] + vals[v] != s:
                continue

            p = prevs[u]
            nv = nexts[v]
            moves += 1

            # Decrease count based on old values
            if p != -1 and vals[p] > vals[u]: unsorted_cnt -= 1
            if vals[u] > vals[v]: unsorted_cnt -= 1
            if nv != -1 and vals[v] > vals[nv]: unsorted_cnt -= 1

            # Merge
            vals[u] = s
            nexts[u] = nv
            if nv != -1: prevs[nv] = u
            removed[v] = True

            # Increase count based on new sum
            if p != -1 and vals[p] > vals[u]: unsorted_cnt += 1
            if nv != -1 and vals[u] > vals[nv]: unsorted_cnt += 1

            if unsorted_cnt == 0: break

            if p != -1: heapq.heappush(pq, (vals[p] + vals[u], p))
            if nv != -1: heapq.heappush(pq, (vals[u] + vals[nv], u))

        return moves

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumPairRemoval = function(nums) {
    const n = nums.length;
    if (n <= 1) return 0;

    let vals = nums.map(BigInt);
    let nexts = Array.from({ length: n }, (_, i) => i + 1);
    let prevs = Array.from({ length: n }, (_, i) => i - 1);
    nexts[n - 1] = -1;
    let removed = new Array(n).fill(false);

    // Using a simple Min-Priority Queue implementation
    const pq = new MinPriorityQueue({ priority: (x) => x.sum });

    let unsorted_cnt = 0;
    for (let i = 0; i < n - 1; i++) {
        if (vals[i] > vals[i + 1]) unsorted_cnt++;
        pq.enqueue({ sum: vals[i] + vals[i + 1], idx: i });
    }

    if (unsorted_cnt === 0) return 0;

    let moves = 0;
    while (unsorted_cnt > 0 && !pq.isEmpty()) {
        let { sum, idx: u } = pq.dequeue().element;

        if (removed[u]) continue;
        let v = nexts[u];
        if (v === -1 || removed[v] || (vals[u] + vals[v] !== sum)) continue;

        let p = prevs[u];
        let nv = nexts[v];
        moves++;

        if (p !== -1 && vals[p] > vals[u]) unsorted_cnt--;
        if (vals[u] > vals[v]) unsorted_cnt--;
        if (nv !== -1 && vals[v] > vals[nv]) unsorted_cnt--;

        vals[u] = sum;
        nexts[u] = nv;
        if (nv !== -1) prevs[nv] = u;
        removed[v] = true;

        if (p !== -1 && vals[p] > vals[u]) unsorted_cnt++;
        if (nv !== -1 && vals[u] > vals[nv]) unsorted_cnt++;

        if (unsorted_cnt === 0) break;

        if (p !== -1) pq.enqueue({ sum: vals[p] + vals[u], idx: p });
        if (nv !== -1) pq.enqueue({ sum: vals[u] + vals[nv], idx: u });
    }

    return moves;
};

---

Key Takeaways

• Greedy Approximation: When a problem asks for the "minimum sum" or "smallest" element repeatedly, a Priority Queue is usually the right tool to keep complexity at .
• Lazy Deletion: Instead of removing items from a Priority Queue (which is difficult), we mark elements as removed and skip them when they appear at the top of the heap.
• Linked Lists via Arrays: Using prev and next arrays to simulate a doubly linked list allows for removal and neighbor lookup.

---

Final Thoughts

This problem is a classic example of how "simulation" tasks can be optimized. In a real-world software engineering context, this logic is similar to memory coalescing in operating systems or text buffer management in editors, where adjacent small chunks are merged to form larger, more useful segments. Mastering the combination of a Priority Queue and a Linked List will make you stand out in high-level technical interviews.