Minimum Pair Removal to Sort Array II

hard linked list heap simulation

Problem

You may repeatedly: pick the adjacent pair with the minimum sum (ties broken by the leftmost pair), and replace both elements with their sum. Return the minimum number of operations needed to make nums non-decreasing (every element ≥ the one before it).

Inputnums = [5, 2, 3, 1]

Output2

(3,1) has min sum 4 → [5,2,4]. Then (2,4) has min sum 6 → [5,6], now non-decreasing.

nums (comma-separated integers)

import heapq

def minimumPairRemoval(nums):
    n = len(nums)
    if n <= 1:
        return 0
    prv = [i - 1 for i in range(n)]            # doubly linked list
    nxt = [i + 1 if i + 1 < n else -1 for i in range(n)]
    val = list(nums)
    alive = [True] * n
    bad = sum(1 for i in range(n - 1) if val[i] > val[i + 1])
    heap = [(val[i] + val[i + 1], i) for i in range(n - 1)]
    heapq.heapify(heap)                         # min-heap by (sum, left index)
    ops = 0
    while bad > 0:                              # not yet non-decreasing
        while heap:                             # skip stale pairs
            s, i = heap[0]
            j = nxt[i]
            if not alive[i] or j == -1 or val[i] + val[j] != s:
                heapq.heappop(heap); continue
            break
        s, i = heapq.heappop(heap)
        j = nxt[i]; p = prv[i]; k = nxt[j]      # neighbours around the pair
        if p != -1 and val[p] > val[i]: bad -= 1
        if val[i] > val[j]:            bad -= 1
        if k != -1 and val[j] > val[k]: bad -= 1
        val[i] += val[j]                        # merge j into i
        alive[j] = False
        nxt[i] = k
        if k != -1: prv[k] = i
        if p != -1 and val[p] > val[i]: bad += 1
        if k != -1 and val[i] > val[k]: bad += 1
        if p != -1: heapq.heappush(heap, (val[p] + val[i], p))
        if k != -1: heapq.heappush(heap, (val[i] + val[k], i))
        ops += 1
    return ops

function minimumPairRemoval(nums) {
  const n = nums.length;
  if (n <= 1) return 0;
  const prv = Array.from({length: n}, (_, i) => i - 1);   // linked list
  const nxt = Array.from({length: n}, (_, i) => i + 1 < n ? i + 1 : -1);
  const val = nums.slice(), alive = Array(n).fill(true);
  let bad = 0;
  for (let i = 0; i < n - 1; i++) if (val[i] > val[i + 1]) bad++;
  const heap = new MinHeap();                              // (sum, leftIdx)
  for (let i = 0; i < n - 1; i++) heap.push([val[i] + val[i + 1], i]);
  let ops = 0;
  while (bad > 0) {                                        // not sorted yet
    let s, i;
    while (true) {                                         // skip stale pairs
      [s, i] = heap.peek();
      const j = nxt[i];
      if (!alive[i] || j === -1 || val[i] + val[j] !== s) { heap.pop(); continue; }
      break;
    }
    heap.pop();
    const j = nxt[i], p = prv[i], k = nxt[j];              // neighbours
    if (p !== -1 && val[p] > val[i]) bad--;
    if (val[i] > val[j]) bad--;
    if (k !== -1 && val[j] > val[k]) bad--;
    val[i] += val[j];                                      // merge j into i
    alive[j] = false; nxt[i] = k;
    if (k !== -1) prv[k] = i;
    if (p !== -1 && val[p] > val[i]) bad++;
    if (k !== -1 && val[i] > val[k]) bad++;
    if (p !== -1) heap.push([val[p] + val[i], p]);
    if (k !== -1) heap.push([val[i] + val[k], i]);
    ops++;
  }
  return ops;
}

int minimumPairRemoval(int[] nums) {
    int n = nums.length;
    if (n <= 1) return 0;
    int[] prv = new int[n], nxt = new int[n];               // linked list
    long[] val = new long[n];
    boolean[] alive = new boolean[n];
    for (int i = 0; i < n; i++) {
        prv[i] = i - 1; nxt[i] = i + 1 < n ? i + 1 : -1;
        val[i] = nums[i]; alive[i] = true;
    }
    int bad = 0;
    for (int i = 0; i < n - 1; i++) if (val[i] > val[i + 1]) bad++;
    // min-heap by (sum, leftIdx)
    PriorityQueue<long[]> heap = new PriorityQueue<>(
        (a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1]));
    for (int i = 0; i < n - 1; i++) heap.add(new long[]{val[i] + val[i + 1], i});
    int ops = 0;
    while (bad > 0) {                                        // not sorted yet
        long[] top;
        while (true) {                                      // skip stale pairs
            top = heap.peek(); int i = (int) top[1], j = nxt[i];
            if (!alive[i] || j == -1 || val[i] + val[j] != top[0]) { heap.poll(); continue; }
            break;
        }
        heap.poll();
        int i = (int) top[1], j = nxt[i], p = prv[i], k = nxt[j];
        if (p != -1 && val[p] > val[i]) bad--;
        if (val[i] > val[j]) bad--;
        if (k != -1 && val[j] > val[k]) bad--;
        val[i] += val[j]; alive[j] = false; nxt[i] = k;     // merge j into i
        if (k != -1) prv[k] = i;
        if (p != -1 && val[p] > val[i]) bad++;
        if (k != -1 && val[i] > val[k]) bad++;
        if (p != -1) heap.add(new long[]{val[p] + val[i], p});
        if (k != -1) heap.add(new long[]{val[i] + val[k], i});
        ops++;
    }
    return ops;
}

int minimumPairRemoval(vector<int>& nums) {
    int n = nums.size();
    if (n <= 1) return 0;
    vector<int> prv(n), nxt(n); vector<long long> val(n);
    vector<char> alive(n, 1);
    for (int i = 0; i < n; i++) {                            // linked list
        prv[i] = i - 1; nxt[i] = i + 1 < n ? i + 1 : -1; val[i] = nums[i];
    }
    int bad = 0;
    for (int i = 0; i < n - 1; i++) if (val[i] > val[i + 1]) bad++;
    // min-heap by (sum, leftIdx)
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> heap;
    for (int i = 0; i < n - 1; i++) heap.push({val[i] + val[i + 1], i});
    int ops = 0;
    while (bad > 0) {                                        // not sorted yet
        long long s; int i, j;
        while (true) {                                      // skip stale pairs
            s = heap.top().first; i = heap.top().second; j = nxt[i];
            if (!alive[i] || j == -1 || val[i] + val[j] != s) { heap.pop(); continue; }
            break;
        }
        heap.pop();
        j = nxt[i]; int p = prv[i], k = nxt[j];             // neighbours
        if (p != -1 && val[p] > val[i]) bad--;
        if (val[i] > val[j]) bad--;
        if (k != -1 && val[j] > val[k]) bad--;
        val[i] += val[j]; alive[j] = 0; nxt[i] = k;         // merge j into i
        if (k != -1) prv[k] = i;
        if (p != -1 && val[p] > val[i]) bad++;
        if (k != -1 && val[i] > val[k]) bad++;
        if (p != -1) heap.push({val[p] + val[i], p});
        if (k != -1) heap.push({val[i] + val[k], i});
        ops++;
    }
    return ops;
}

Explanation

Each operation deletes one element (two become one), so we want to do as few merges as possible. The greedy rule is fixed for us: always merge the leftmost adjacent pair of minimum sum. So this is a pure simulation — the only challenge is doing each step quickly when the array can be up to 10⁵ long.

Naively scanning for the minimum pair every operation is O(n) per step, which is too slow. Instead we keep three structures in sync:

A doubly-linked list (prv / nxt index arrays) over the original positions. Merging a pair just splices a node out in O(1) — no shifting of a real array. An alive flag marks deleted nodes.

A min-heap of (pairSum, leftIndex) for adjacent pairs. The heap's top is the candidate min-sum pair. Because we never delete from the middle of a heap, entries can go stale (one endpoint was merged away, or the stored sum no longer matches the live values). Before trusting the top we re-validate it: if the left node is dead, has no right neighbour, or the recomputed sum differs, we pop and skip it. Only fresh, leftmost-among-ties entries survive. (The heap order (sum, index) guarantees ties pick the smaller index = leftmost.)

A counter bad = how many adjacent pairs are currently descending (val[i] > val[next]). The array is non-decreasing exactly when bad == 0, so we loop until then. A merge only touches the pair itself and its two outer neighbours, so we adjust bad by removing the three old relationships and adding back the two new ones in O(1) — far cheaper than re-checking sortedness each round.

When we merge node j into node i: set val[i] += val[j], mark j dead, relink i to k = nxt[j], and push the two brand-new adjacent pairs (p,i) and (i,k) onto the heap. Increment ops. Each element is created once and deleted at most once, and every heap entry is popped at most once, giving an overall O(n log n) run.

Time: O(n log n) Space: O(n)