3510. Minimum Pair Removal to Sort Array II

/**
 * Problem: LeetCode 3510 - Minimum Pair Removal to Sort Array II
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.PriorityQueue;

class Solution {
    // Helper class to store candidate adjacent pair in PriorityQueue
    private static class Pair implements Comparable<Pair> {
        long sum;
        int id;
        int ver;

        Pair(long sum, int id, int ver) {
            this.sum = sum;
            this.id = id;
            this.ver = ver;
        }

        @Override
        public int compareTo(Pair other) {
            if (this.sum != other.sum) {
                return Long.compare(this.sum, other.sum);
            }
            return Integer.compare(this.id, other.id);
        }
    }

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

        long[] val = new long[n];
        int[] prev = new int[n];
        int[] next = new int[n];
        boolean[] deleted = new boolean[n];
        int[] version = new int[n];

        for (int i = 0; i < n; i++) {
            val[i] = nums[i];
            prev[i] = i - 1;
            next[i] = (i + 1 < n) ? i + 1 : -1;
        }

        int descents = 0;
        for (int i = 0; i < n - 1; i++) {
            if (val[i] > val[i + 1]) {
                descents++;
            }
        }

        if (descents == 0) return 0;

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

        int ops = 0;
        while (descents > 0 && !pq.isEmpty()) {
            Pair top = pq.poll();
            int u = top.id;

            if (deleted[u] || top.ver != version[u]) continue;
            int v = next[u];
            if (v == -1 || deleted[v]) continue;
            if (top.sum != val[u] + val[v]) continue;

            int p = prev[u];
            int w = next[v];

            // Remove previous inversion contributions
            if (p != -1 && val[p] > val[u]) descents--;
            if (val[u] > val[v]) descents--;
            if (w != -1 && val[v] > val[w]) descents--;

            // Merge u and v
            val[u] += val[v];
            deleted[v] = true;
            next[u] = w;
            if (w != -1) {
                prev[w] = u;
            }

            // Add new inversion contributions
            if (p != -1 && val[p] > val[u]) descents++;
            if (w != -1 && val[u] > val[w]) descents++;

            version[u]++;
            ops++;

            if (descents == 0) break;

            // Re-push updated adjacent pairs into PriorityQueue
            if (p != -1) {
                version[p]++;
                pq.offer(new Pair(val[p] + val[u], p, version[p]));
            }
            if (w != -1) {
                pq.offer(new Pair(val[u] + val[w], u, version[u]));
            }
        }

        return ops;
    }
}

"""
Problem: LeetCode 3510 - Minimum Pair Removal to Sort Array II
Difficulty: Hard
Language: Python
Author: CodeByTushu
"""
import heapq
from typing import List

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

        val = [int(x) for x in nums]
        prev = [i - 1 for i in range(n)]
        nxt = [i + 1 if i + 1 < n else -1 for i in range(n)]
        deleted = [False] * n
        version = [0] * n

        descents = 0
        for i in range(n - 1):
            if val[i] > val[i + 1]:
                descents += 1

        if descents == 0:
            return 0

        # Heap elements: (sum, node_id, version)
        pq = [(val[i] + val[i + 1], i, 0) for i in range(n - 1)]
        heapq.heapify(pq)

        ops = 0
        while descents > 0 and pq:
            pair_sum, u, ver = heapq.heappop(pq)

            if deleted[u] or ver != version[u]:
                continue
            v = nxt[u]
            if v == -1 or deleted[v]:
                continue
            if pair_sum != val[u] + val[v]:
                continue

            p = prev[u]
            w = nxt[v]

            # Remove previous inversion contributions
            if p != -1 and val[p] > val[u]:
                descents -= 1
            if val[u] > val[v]:
                descents -= 1
            if w != -1 and val[v] > val[w]:
                descents -= 1

            # Merge u and v
            val[u] += val[v]
            deleted[v] = True
            nxt[u] = w
            if w != -1:
                prev[w] = u

            # Add new inversion contributions
            if p != -1 and val[p] > val[u]:
                descents += 1
            if w != -1 and val[u] > val[w]:
                descents += 1

            version[u] += 1
            ops += 1

            if descents == 0:
                break

            # Push updated adjacent pairs
            if p != -1:
                version[p] += 1
                heapq.heappush(pq, (val[p] + val[u], p, version[p]))
            if w != -1:
                heapq.heappush(pq, (val[u] + val[w], u, version[u]))

        return ops

/**
 * Problem: LeetCode 3510 - Minimum Pair Removal to Sort Array II
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <queue>

using namespace std;

class Solution {
    struct Pair {
        long long sum;
        int id;
        int ver;

        bool operator>(const Pair& other) const {
            if (sum != other.sum) {
                return sum > other.sum;
            }
            return id > other.id;
        }
    };

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

        vector<long long> val(n);
        vector<int> prev(n);
        vector<int> next(n);
        vector<bool> deleted(n, false);
        vector<int> version(n, 0);

        for (int i = 0; i < n; i++) {
            val[i] = nums[i];
            prev[i] = i - 1;
            next[i] = (i + 1 < n) ? i + 1 : -1;
        }

        int descents = 0;
        for (int i = 0; i < n - 1; i++) {
            if (val[i] > val[i + 1]) {
                descents++;
            }
        }

        if (descents == 0) return 0;

        priority_queue<Pair, vector<Pair>, greater<Pair>> pq;
        for (int i = 0; i < n - 1; i++) {
            pq.push({val[i] + val[i + 1], i, 0});
        }

        int ops = 0;
        while (descents > 0 && !pq.empty()) {
            Pair top = pq.top();
            pq.pop();
            int u = top.id;

            if (deleted[u] || top.ver != version[u]) continue;
            int v = next[u];
            if (v == -1 || deleted[v]) continue;
            if (top.sum != val[u] + val[v]) continue;

            int p = prev[u];
            int w = next[v];

            // Remove old inversion contributions
            if (p != -1 && val[p] > val[u]) descents--;
            if (val[u] > val[v]) descents--;
            if (w != -1 && val[v] > val[w]) descents--;

            // Merge u and v
            val[u] += val[v];
            deleted[v] = true;
            next[u] = w;
            if (w != -1) {
                prev[w] = u;
            }

            // Add new inversion contributions
            if (p != -1 && val[p] > val[u]) descents++;
            if (w != -1 && val[u] > val[w]) descents++;

            version[u]++;
            ops++;

            if (descents == 0) break;

            // Push updated adjacent pairs
            if (p != -1) {
                version[p]++;
                pq.push({val[p] + val[u], p, version[p]});
            }
            if (w != -1) {
                pq.push({val[u] + val[w], u, version[u]});
            }
        }

        return ops;
    }
};

/**
 * Problem: LeetCode 3510 - Minimum Pair Removal to Sort Array II
 * Difficulty: Hard
 * Language: JavaScript
 * Author: CodeByTushu
 */
class MinHeap {
    constructor() {
        this.heap = [];
    }
    push(item) {
        this.heap.push(item);
        this._siftUp(this.heap.length - 1);
    }
    pop() {
        if (this.heap.length === 0) return null;
        const top = this.heap[0];
        const last = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = last;
            this._siftDown(0);
        }
        return top;
    }
    size() {
        return this.heap.length;
    }
    _compare(a, b) {
        if (a.sum !== b.sum) {
            return a.sum < b.sum ? -1 : 1;
        }
        return a.id < b.id ? -1 : (a.id > b.id ? 1 : 0);
    }
    _siftUp(i) {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this._compare(this.heap[i], this.heap[p]) < 0) {
                [this.heap[i], this.heap[p]] = [this.heap[p], this.heap[i]];
                i = p;
            } else break;
        }
    }
    _siftDown(i) {
        const n = this.heap.length;
        while ((i << 1) + 1 < n) {
            let left = (i << 1) + 1;
            let right = left + 1;
            let best = i;
            if (this._compare(this.heap[left], this.heap[best]) < 0) best = left;
            if (right < n && this._compare(this.heap[right], this.heap[best]) < 0) best = right;
            if (best !== i) {
                [this.heap[i], this.heap[best]] = [this.heap[best], this.heap[i]];
                i = best;
            } else break;
        }
    }
}

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

    const val = nums.map(x => BigInt(x));
    const prev = new Int32Array(n);
    const next = new Int32Array(n);
    const deleted = new Uint8Array(n);
    const version = new Int32Array(n);

    for (let i = 0; i < n; i++) {
        prev[i] = i - 1;
        next[i] = i + 1 < n ? i + 1 : -1;
    }

    let descents = 0;
    for (let i = 0; i < n - 1; i++) {
        if (val[i] > val[i + 1]) descents++;
    }

    if (descents === 0) return 0;

    const pq = new MinHeap();
    for (let i = 0; i < n - 1; i++) {
        pq.push({ sum: val[i] + val[i + 1], id: i, ver: 0 });
    }

    let ops = 0;
    while (descents > 0 && pq.size() > 0) {
        const top = pq.pop();
        const u = top.id;

        if (deleted[u] || top.ver !== version[u]) continue;
        const v = next[u];
        if (v === -1 || deleted[v]) continue;
        if (top.sum !== val[u] + val[v]) continue;

        const p = prev[u];
        const w = next[v];

        // Remove old descent contributions
        if (p !== -1 && val[p] > val[u]) descents--;
        if (val[u] > val[v]) descents--;
        if (w !== -1 && val[v] > val[w]) descents--;

        // Merge u and v
        val[u] = val[u] + val[v];
        deleted[v] = 1;
        next[u] = w;
        if (w !== -1) prev[w] = u;

        // Add new descent contributions
        if (p !== -1 && val[p] > val[u]) descents++;
        if (w !== -1 && val[u] > val[w]) descents++;

        version[u]++;
        ops++;

        if (descents === 0) break;

        // Push updated adjacent pairs
        if (p !== -1) {
            version[p]++;
            pq.push({ sum: val[p] + val[u], id: p, ver: version[p] });
        }
        if (w !== -1) {
            pq.push({ sum: val[u] + val[w], id: u, ver: version[u] });
        }
    }

    return ops;
};