Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The required merge always uses the smallest adjacent-pair sum, with leftmost tie-breaking. A heap finds that pair, while a doubly linked list supports local removal. To detect when the sequence becomes nondecreasing, count descending adjacent edges rather than rescanning the whole sequence.

Approach

Create linked nodes carrying values and original indices. Insert every adjacent pair into a min-heap keyed by its sum and left index, and count adjacent inversions. Original indices preserve current left-to-right order because merging retains the left node.

While inversions remain, pop heap entries until the left node is alive, has a live successor, and their current sum matches the stored sum. Discard entries failing those checks. A historical entry remains usable even if its successor changed, provided the current sum matches: its sum and left-index priority are exactly those of the current pair. Remove the inversion contributions of the three edges touching the pair, merge into the left node, and unlink the right node. Then add the contributions of the two new neighboring edges and push their pair sums.

Only local relationships change after a merge. Stop when the inversion count reaches zero and return the number of merges. Every current adjacent pair has a matching heap entry, so the heap enforces the prescribed choice. Only a constant number of entries are added per merge, and each is popped at most once.

class Node:
    def __init__(self, val: int, i: int):
        self.val = val
        self.prev = None
        self.next = None
        self.alive = True # for lazy deletion
        self.i = i

class Solution:
    def minimumPairRemoval(self, nums: List[int]) -> int:
        n = len(nums)
        dll = Node(nums[0], 0)
        curr = dll
        nodes = [dll]

        for i in range(1, n):
            node = Node(nums[i], i)
            curr.next = node
            node.prev = curr
            curr = node
            nodes.append(node)

        inversions = 0
        heap = []

        for i in range(1, n):
            if nums[i] < nums[i - 1]:
                inversions += 1
            heapq.heappush(heap, (nums[i] + nums[i - 1], i - 1, nodes[i].prev))

        ops = 0

        while inversions:
            # lazy deletion
            while True:
                total, i, left = heapq.heappop(heap)
                right = left.next
                if not left.alive or not right or not right.alive:
                    continue
                if left.val + right.val != total:
                    continue
                break

            # remove left, right, and right.next possible inversions
            if left.prev and left.val < left.prev.val:
                inversions -= 1
            if right.val < left.val:
                inversions -= 1
            if right.next and right.next.val < right.val:
                inversions -= 1

            # update left and remove right
            left.val = total
            right.alive = False
            left.next = (right.next if right and right.next else None)
            if right.next:
                right.next.prev = left

            # add 2 new possible inversions and adjacent pairs with new left
            if left.prev and left.val < left.prev.val:
                inversions += 1
            if left.next and left.next.val < left.val:
                inversions += 1
            if left.prev:
                heapq.heappush(heap, (left.prev.val + left.val, left.prev.i, left.prev))
            if left.next:
                heapq.heappush(heap, (left.val + left.next.val, left.i, left))
            ops += 1

        return ops

Complexity analysis

Let n = nums.length. Time: O(n log n). Auxiliary space: O(n).