Description
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 <= 105-109 <= nums[i] <= 109
Solutions
This is an optimized greedy solution using a priority queue and doubly-linked list to efficiently handle pair merging. Instead of rescanning the array each time, it maintains a priority queue of all adjacent pairs sorted by their sum and tracks how many descending positions remain using decreaseCount. When merging two adjacent nodes, it updates neighboring pairs in the priority queue and adjusts the decreaseCount based on whether the merge creates or eliminates inversions. The merged array tracks which original indices have been consumed to avoid processing stale pairs from the queue. This approach achieves far better performance by eliminating redundant scans and array manipulations, allowing it to handle large inputs efficiently.
class Node extends DoublyLinkedListNode {
value;
left;
constructor(value, left) {
super(value);
this.value = value;
this.left = left;
}
}
var minimumPairRemoval = function (nums) {
const pq = new PriorityQueue((a, b) =>
a.cost === b.cost ? a.first.left - b.first.left : a.cost - b.cost,
);
const list = new DoublyLinkedList();
const merged = new Array(nums.length).fill(false);
let decreaseCount = 0;
let count = 0;
list.insertLast(new Node(nums[0], 0));
for (let i = 1; i < nums.length; i++) {
list.insertLast(new Node(nums[i], i));
const curr = list.tail();
pq.enqueue({
first: curr.getPrev(),
second: curr,
cost: nums[i] + nums[i - 1],
});
if (nums[i - 1] > nums[i]) {
decreaseCount++;
}
}
while (decreaseCount > 0) {
const { first, second, cost } = pq.dequeue();
if (
merged[first.left] ||
merged[second.left] ||
first.value + second.value !== cost
)
continue;
count++;
if (first.value > second.value) {
decreaseCount--;
}
const prev = first.getPrev();
const next = second.getNext();
if (prev) {
if (prev.value > first.value && prev.value <= cost) {
decreaseCount--;
}
if (prev.value <= first.value && prev.value > cost) {
decreaseCount++;
}
pq.enqueue({
first: prev,
second: first,
cost: prev.value + cost,
});
}
if (next) {
if (second.value > next.value && cost <= next.value) {
decreaseCount--;
}
if (second.value <= next.value && cost > next.value) {
decreaseCount++;
}
pq.enqueue({
first: first,
second: next,
cost: cost + next.value,
});
}
list.remove(second);
first.value = cost;
merged[second.left] = true;
}
return count;
};