Skip to content

Instantly share code, notes, and snippets.

@tatsuyax25

tatsuyax25/minimumPairRemoval.js

Created January 23, 2026 18:50
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save tatsuyax25/6cb3772b8abd8746a1bb51c84eb255e6 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save tatsuyax25/6cb3772b8abd8746a1bb51c84eb255e6 to your computer and use it in GitHub Desktop.
Download ZIP
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 numbe
Raw
minimumPairRemoval.js
/**
* Simulates the "minimum adjacent sum merge" process efficiently using:
* - A doubly linked list (prev/next) to track alive indices
* - Versioning (ver[]) to invalidate stale heap entries
* - A custom typed min‑heap for fast pair selection
* - An inversion counter to detect when the array becomes non‑decreasing
*
* @param {number[]} nums
* @return {number}
*/
var minimumPairRemoval = function(nums) {
const n = nums.length;
if (n <= 1) return 0;
// Current values after merges
const val = nums.slice();
// Version numbers for each index (incremented when val[i] changes)
const ver = new Uint32Array(n);
// Doubly linked list over indices 0..n-1
const prev = new Int32Array(n);
const next = new Int32Array(n);
// Marker for removed nodes
const DEAD = -2;
// Initialize linked list
for (let i = 0; i < n; i++) {
prev[i] = i - 1;
next[i] = i + 1 < n ? i + 1 : -1;
}
// Min‑heap of candidate pairs (sum, left, right, verLeft, verRight)
const heap = new TypedMinHeap(Math.max(16, n * 2));
// Push a pair (i, j) into the heap if both are alive
const pushPair = (i, j) => {
if (i < 0 || j < 0) return;
if (next[i] === DEAD || next[j] === DEAD) return;
heap.push(val[i] + val[j], i, j, ver[i], ver[j]);
};
// Count initial inversions (places where val[i] > val[i+1])
let invCount = 0;
for (let i = 0; i < n - 1; i++) {
if (val[i] > val[i + 1]) invCount++;
pushPair(i, i + 1);
}
let removals = 0;
// Process until array becomes non‑decreasing
while (heap.len && invCount > 0) {
const top = heap.pop(); // [sum, left, right, verLeft, verRight]
if (!top) break;
const sum = top[0];
const left = top[1] | 0;
const right = top[2] | 0;
const vL = top[3] | 0;
const vR = top[4] | 0;
// Validate that this heap entry is still relevant
if (next[left] === DEAD || next[right] === DEAD) continue;
if (next[left] !== right) continue; // must still be adjacent
if (ver[left] !== vL || ver[right] !== vR) continue; // versions must match
if (val[left] + val[right] !== sum) continue; // sum must still match
// Adjacent nodes around the merge region
const a = prev[left]; // left neighbor
const b = left; // merge target
const c = right; // node being removed
const d = next[right]; // right neighbor
// Remove inversion contributions for edges that will disappear
if (a !== -1) {
const r = next[a];
if (r >= 0 && val[a] > val[r]) invCount--;
}
{
const r = next[b];
if (r >= 0 && val[b] > val[r]) invCount--;
}
{
const r = next[c];
if (r >= 0 && val[c] > val[r]) invCount--;
}
// Perform the merge: left absorbs right
val[left] += val[right];
ver[left]++; // bump version to invalidate stale heap entries
removals++;
// Remove "right" from the linked list
next[right] = DEAD;
next[left] = d;
if (d !== -1) prev[d] = left;
// Re‑add inversion contributions for new edges
if (a !== -1) {
const r = next[a];
if (r >= 0 && val[a] > val[r]) invCount++;
}
{
const r = next[b];
if (r >= 0 && val[b] > val[r]) invCount++;
}
// Push new adjacent pairs created by the merge
if (a !== -1) pushPair(a, left);
if (d !== -1) pushPair(left, d);
}
return removals;
};
/**
* High‑performance min‑heap specialized for storing 5‑element nodes:
* [sum, leftIndex, rightIndex, verLeft, verRight]
*
* Uses a flat Float64Array for speed and predictable memory layout.
*/
class TypedMinHeap {
constructor(cap) {
this.nodeSize = 5;
this.len = 0;
this.cap = cap;
this.buf = new Float64Array(cap * 5);
this.tmp = new Float64Array(5); // reusable output buffer
}
// Insert a new node
push(sum, i, j, vL, vR) {
if (this.len >= this.cap) this._grow();
let idx = this.len++;
let base = idx * 5;
const b = this.buf;
// Write node
b[base] = sum;
b[base + 1] = i;
b[base + 2] = j;
b[base + 3] = vL;
b[base + 4] = vR;
// Bubble up
while (idx > 0) {
const p = (idx - 1) >> 1;
const pb = p * 5;
const sb = idx * 5;
const sumA = b[sb], sumB = b[pb];
// Compare by sum, then by left index
if (sumA > sumB || (sumA === sumB && b[sb + 1] >= b[pb + 1])) break;
// Swap
for (let k = 0; k < 5; k++) {
const t = b[sb + k];
b[sb + k] = b[pb + k];
b[pb + k] = t;
}
idx = p;
}
}
// Remove and return the smallest node
pop() {
if (this.len === 0) return null;
const out = this.tmp;
const b = this.buf;
// Copy root into output buffer
for (let k = 0; k < 5; k++) out[k] = b[k];
const lastIdx = --this.len;
if (lastIdx === 0) return out;
// Move last node to root
const lb = lastIdx * 5;
for (let k = 0; k < 5; k++) b[k] = b[lb + k];
// Sift down
let idx = 0;
const len = this.len;
while (true) {
const l = idx * 2 + 1;
if (l >= len) break;
const r = l + 1;
let s = l;
const sb = s * 5;
const ib = idx * 5;
// Choose better child
if (r < len) {
const rb = r * 5;
const sumL = b[sb], sumR = b[rb];
const betterR =
sumR < sumL || (sumR === sumL && b[rb + 1] < b[sb + 1]);
if (betterR) s = r;
}
const sb2 = s * 5;
const sumS = b[sb2], sumI = b[ib];
// If parent is already <= child, stop
if (sumS > sumI || (sumS === sumI && b[sb2 + 1] >= b[ib + 1])) break;
// Swap parent and child
for (let k = 0; k < 5; k++) {
const t = b[ib + k];
b[ib + k] = b[sb2 + k];
b[sb2 + k] = t;
}
idx = s;
}
return out;
}
// Double heap capacity
_grow() {
const old = this.buf;
this.cap *= 2;
this.buf = new Float64Array(this.cap * 5);
this.buf.set(old);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment