Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The operation is deterministic: choose the adjacent pair with the smallest sum, breaking ties by the leftmost pair. There is no alternative merge sequence to optimize, so simulate until the array becomes nondecreasing.

Approach

At the start of each round, compare the current array with its sorted copy. If they match, return the number of operations already performed. Otherwise scan all adjacent pairs from left to right, retaining the pair with the smallest sum. Update the selected pair only for a strictly smaller sum, preserving the leftmost choice on ties.

Replace the pair's left element by their sum and remove its right element, then increment the operation count. Each merge reduces the array length by one, so termination is guaranteed at the latest when one element remains. The complexity includes repeated sorting for the stopping condition and rebuilding the array after removal, as done in the supplied code.

class Solution:
    def minimumPairRemoval(self, nums: List[int]) -> int:
        ops = 0

        while nums != sorted(nums):
            mn = inf
            sel = -1
            for i in range(1, len(nums)):
                if nums[i] + nums[i - 1] < mn:
                    mn = nums[i] + nums[i - 1]
                    sel = i

            nums[sel - 1] += nums[sel]
            nums = nums[:sel] + nums[sel + 1:]
            ops += 1

        return ops

Complexity analysis

Let n = nums.length. Time: O(n^2 log n) because each of up to n-1 removals sorts the shrinking array for the loop condition. Auxiliary space: O(n) for sort and slice/concatenation temporaries.