3507. Minimum Pair Removal to Sort Array I

EasyArrayHash TableLinked ListDoubly-Linked ListOrdered SetSimulationHeap (Priority Queue)

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an array nums. You can perform the following operation any number of times:

Find the adjacent pair of elements whose sum is the smallest. If there are several pairs that share the same minimum sum, pick the leftmost one among them.
Replace that pair of elements with a single element equal to their sum (this reduces the length of the array by one).

Your task is to return the minimum number of operations required to turn nums into a non-decreasing array.

An array is non-decreasing when every element is greater than or equal to the element immediately before it (whenever a previous element exists). In other words, for each index i (with i ≥ 1), the condition nums[i] >= nums[i - 1] must hold.

Example walkthrough of an operation:

Suppose nums = [5, 2, 3, 1]. The adjacent pairs and their sums are:
- 5 + 2 = 7
- 2 + 3 = 5
- 3 + 1 = 4
The smallest sum is 4, formed by the pair (3, 1). We replace this pair with 4, so the array becomes [5, 2, 4].

You keep applying such operations until the array is non-decreasing, and you count how many operations were used.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

The problem describes a deterministic step-by-step process of merging adjacent pairs with the minimum sum, so direct simulation is the natural approach.

Open in Flowchart

Intuition

The problem statement describes a process step by step, and there's no hidden trick that lets us skip ahead: at every moment we must operate on the leftmost adjacent pair with the minimum sum. Because each operation depends on the current state of the array, and the rule for choosing the pair is fixed and deterministic, the most natural idea is to simply simulate exactly what the problem says.

So we ask ourselves two questions at each step:

Is the array already non-decreasing? If it is, we are done and no more operations are needed. We can check this by scanning the array once and confirming that every element is >= the one before it.
If it is not, which pair do we merge? We scan all adjacent pairs, compute each pair's sum, and keep track of the smallest sum seen so far along with its left index k. Because we only update our best choice when we find a strictly smaller sum (s > t), ties are automatically resolved in favor of the leftmost pair — the first occurrence of the minimum sum is never overwritten by a later equal one.

Once we know where to merge, the action is straightforward: we set arr[k] to the pair's sum and remove the right element arr[k + 1], shrinking the array by one. We then increase our operation counter by one.

We repeat this "check, then merge" cycle until the array becomes non-decreasing. Each operation reduces the array length, and merging two elements into their sum can only make values larger, so the array steadily moves toward being non-decreasing — guaranteeing the loop eventually stops. The final value of the counter is the minimum number of operations, since the rule for each step is forced and leaves us no alternative choices to optimize.

Pattern Learn more about Linked List and Heap (Priority Queue) patterns.

Solution Approach

Solution 1: Simulation

We directly simulate the process described in the problem until the array becomes non-decreasing.

Step 1: Make a working copy and a helper function.

We copy nums into arr so that the original input is left untouched, and we initialize the answer counter ans = 0.

We define a helper function is_non_decreasing(a) that scans the array once: for every index i from 1 to len(a) - 1, if a[i] < a[i - 1], the array is not non-decreasing and we return False. If the scan completes without finding such a violation, we return True. This function tells us when to stop looping.

Step 2: Loop until the array is non-decreasing.

While is_non_decreasing(arr) returns False, we perform one operation:

We start by assuming the best (minimum) sum is the first pair: s = arr[0] + arr[1] and k = 0.
We then iterate i from 1 to len(arr) - 2, computing each adjacent pair sum t = arr[i] + arr[i + 1]. Whenever s > t (a strictly smaller sum is found), we update s = t and k = i. Using strict comparison ensures that, when multiple pairs share the same minimum sum, the leftmost index is kept, because later equal sums never trigger an update.

Step 3: Apply the merge.

After the scan, k is the left index of the chosen pair and s is its sum:

We set arr[k] = s to store the combined value at the left position.
We call arr.pop(k + 1) to remove the right element, which shrinks the array by one.
We increment ans += 1 to count this operation.

Step 4: Return the result.

Once the loop condition fails (the array has become non-decreasing), we return ans, the total number of operations performed.

Data structures and patterns used:

The core data structure is a simple list (arr), where merging is done via in-place assignment plus pop.
The pattern is brute-force simulation: each iteration costs O(n) to check non-decreasing order and O(n) to scan for the minimum-sum pair, plus O(n) for the pop. Since each operation reduces the array length by one, there are at most O(n) operations, giving an overall time complexity of O(n^2). The space complexity is O(n) for the copied array.

Example Walkthrough

Let's trace through the solution using the small example nums = [4, 1, 2, 3].

We copy nums into arr = [4, 1, 2, 3] and set ans = 0.

Operation 1:

First, we check is_non_decreasing([4, 1, 2, 3]). Comparing arr[1] = 1 with arr[0] = 4, we find 1 < 4, so the array is not non-decreasing. We must merge.

Now we scan all adjacent pair sums:

Start with s = arr[0] + arr[1] = 4 + 1 = 5, k = 0.
i = 1: t = arr[1] + arr[2] = 1 + 2 = 3. Since s > t (5 > 3), update s = 3, k = 1.
i = 2: t = arr[2] + arr[3] = 2 + 3 = 5. Since s > t is false (3 > 5 is false), no update.

The minimum sum is 3 at k = 1, the pair (1, 2). We set arr[1] = 3 and pop index 2:

arr becomes [4, 3, 3], and ans = 1.

Operation 2:

Check is_non_decreasing([4, 3, 3]). Comparing arr[1] = 3 with arr[0] = 4, we find 3 < 4, so it is not non-decreasing. We merge again.

Scan adjacent pair sums:

Start with s = arr[0] + arr[1] = 4 + 3 = 7, k = 0.
i = 1: t = arr[1] + arr[2] = 3 + 3 = 6. Since s > t (7 > 6), update s = 6, k = 1.

The minimum sum is 6 at k = 1, the pair (3, 3). We set arr[1] = 6 and pop index 2:

arr becomes [4, 6], and ans = 2.

Final check:

Check is_non_decreasing([4, 6]). Comparing arr[1] = 6 with arr[0] = 4, we find 6 >= 4. The array is non-decreasing, so the loop stops.

We return ans = 2.

This demonstrates the key mechanics of the approach: at each step we verify whether the array is already sorted, and if not, we locate the leftmost minimum-sum adjacent pair (using strict comparison s > t to preserve the leftmost tie), merge it into a single larger value, and count the operation. Merging always produces a larger value, steadily pushing the array toward being non-decreasing until the process terminates with the answer of 2 operations.

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def minimumPairRemoval(self, nums: List[int]) -> int:
6        # Work on a copy so the original input is left untouched.
7        arr = nums[:]
8        # Counter for the number of merge operations performed.
9        operations = 0
10
11        def is_non_decreasing(a: List[int]) -> bool:
12            # An array is non-decreasing if every element is >= its predecessor.
13            for i in range(1, len(a)):
14                if a[i] < a[i - 1]:
15                    return False
16            return True
17
18        # Keep merging adjacent pairs until the array becomes non-decreasing.
19        while not is_non_decreasing(arr):
20            # Track the index of the pair with the minimum sum.
21            min_index = 0
22            # Initialize with the sum of the first adjacent pair.
23            min_sum = arr[0] + arr[1]
24
25            # Scan all remaining adjacent pairs to find the smallest sum.
26            for i in range(1, len(arr) - 1):
27                current_sum = arr[i] + arr[i + 1]
28                # Strictly smaller sum: update the best candidate (keeps leftmost on ties).
29                if min_sum > current_sum:
30                    min_sum = current_sum
31                    min_index = i
32
33            # Replace the left element of the chosen pair with their sum.
34            arr[min_index] = min_sum
35            # Remove the right element of the pair, effectively merging them.
36            arr.pop(min_index + 1)
37            # Count this merge operation.
38            operations += 1
39
40        return operations
41

1class Solution {
2    /**
3     * Repeatedly merges the adjacent pair with the smallest sum until the
4     * array becomes non-decreasing, returning the number of merge operations.
5     *
6     * @param nums the input array
7     * @return the minimum number of adjacent pair removals (merges) required
8     */
9    public int minimumPairRemoval(int[] nums) {
10        // Convert the input array into a mutable list for easy removal of elements.
11        List<Integer> list = new ArrayList<>();
12        for (int value : nums) {
13            list.add(value);
14        }
15
16        int operations = 0;
17
18        // Keep merging until the list is sorted in non-decreasing order.
19        while (!isNonDecreasing(list)) {
20            // Track the index of the pair with the minimum sum and that sum itself.
21            int minIndex = 0;
22            int minSum = list.get(0) + list.get(1);
23
24            // Scan all adjacent pairs to find the one with the smallest sum.
25            // The leftmost pair wins ties since we only update on a strictly smaller sum.
26            for (int i = 1; i < list.size() - 1; ++i) {
27                int currentSum = list.get(i) + list.get(i + 1);
28                if (minSum > currentSum) {
29                    minSum = currentSum;
30                    minIndex = i;
31                }
32            }
33
34            // Merge the chosen pair: replace the left element with the sum
35            // and remove the right element.
36            list.set(minIndex, minSum);
37            list.remove(minIndex + 1);
38
39            // Count this merge operation.
40            ++operations;
41        }
42
43        return operations;
44    }
45
46    /**
47     * Checks whether the given list is sorted in non-decreasing order.
48     *
49     * @param list the list to check
50     * @return true if every element is greater than or equal to its predecessor
51     */
52    private boolean isNonDecreasing(List<Integer> list) {
53        for (int i = 1; i < list.size(); ++i) {
54            if (list.get(i) < list.get(i - 1)) {
55                return false;
56            }
57        }
58        return true;
59    }
60}
61

1class Solution {
2public:
3    int minimumPairRemoval(vector<int>& nums) {
4        // Work on a copy so the original input stays untouched.
5        vector<int> arr = nums;
6        int operations = 0;
7
8        // Keep merging until the array becomes non-decreasing.
9        while (!isNonDecreasing(arr)) {
10            // Track the index of the leftmost pair with the minimum sum.
11            int minIndex = 0;
12            int minSum = arr[0] + arr[1];
13
14            // Scan all adjacent pairs to find the smallest sum.
15            for (int i = 1; i + 1 < static_cast<int>(arr.size()); ++i) {
16                int currentSum = arr[i] + arr[i + 1];
17                if (currentSum < minSum) {
18                    minSum = currentSum;
19                    minIndex = i;
20                }
21            }
22
23            // Merge the chosen pair: store the sum and remove the second element.
24            arr[minIndex] = minSum;
25            arr.erase(arr.begin() + (minIndex + 1));
26            ++operations;
27        }
28
29        return operations;
30    }
31
32private:
33    // Returns true if the array is sorted in non-decreasing order.
34    bool isNonDecreasing(const vector<int>& arr) {
35        for (int i = 1; i < static_cast<int>(arr.size()); ++i) {
36            if (arr[i] < arr[i - 1]) {
37                return false;
38            }
39        }
40        return true;
41    }
42};
43

1/**
2 * Returns the minimum number of pair-removal operations required to make the
3 * array non-decreasing.
4 *
5 * In each operation we find the adjacent pair with the smallest sum, replace
6 * the left element of that pair with the sum, and remove the right element.
7 * We repeat until the array is non-decreasing.
8 *
9 * @param nums - The input array of numbers.
10 * @returns The number of operations performed.
11 */
12function minimumPairRemoval(nums: number[]): number {
13    // Work on a copy so the original input is left untouched.
14    const arr: number[] = nums.slice();
15
16    // Counter for the number of operations performed.
17    let operations = 0;
18
19    /**
20     * Checks whether the given array is sorted in non-decreasing order.
21     *
22     * @param values - The array to inspect.
23     * @returns True if every element is >= its predecessor, otherwise false.
24     */
25    const isNonDecreasing = (values: number[]): boolean => {
26        for (let i = 1; i < values.length; i++) {
27            if (values[i] < values[i - 1]) {
28                return false;
29            }
30        }
31        return true;
32    };
33
34    // Keep merging the minimum-sum adjacent pair until the array is sorted.
35    while (!isNonDecreasing(arr)) {
36        // Index of the left element of the adjacent pair with the smallest sum.
37        let minIndex = 0;
38
39        // Smallest adjacent-pair sum found so far (initialized with the first pair).
40        let minSum = arr[0] + arr[1];
41
42        // Scan all remaining adjacent pairs to find the one with the smallest sum.
43        for (let i = 1; i < arr.length - 1; ++i) {
44            const currentSum = arr[i] + arr[i + 1];
45            if (minSum > currentSum) {
46                minSum = currentSum;
47                minIndex = i;
48            }
49        }
50
51        // Replace the left element with the pair sum and remove the right element.
52        arr[minIndex] = minSum;
53        arr.splice(minIndex + 1, 1);
54
55        // Record that an operation has been performed.
56        operations++;
57    }
58
59    return operations;
60}
61

Time and Space Complexity

Time Complexity: O(n^2)

The algorithm operates with an outer while loop and inner operations as follows:

Each iteration of the while loop reduces the array length by exactly 1 (via arr.pop(k + 1)), since two adjacent elements are merged into one. Starting from length n, the loop can run at most O(n) times before the array becomes non-decreasing (in the worst case, until only one element remains).
Inside each while iteration, the work performed is:
- is_non_decreasing(arr): scans the entire array, costing O(n).
- The for loop finding the minimum adjacent pair sum: scans the array, costing O(n).
- arr.pop(k + 1): shifting elements after the removed position, costing O(n).
Each while iteration therefore costs O(n), and with O(n) iterations, the total time complexity is O(n) * O(n) = O(n^2).

Space Complexity: O(n)

The auxiliary array arr = nums[:] creates a copy of the input, requiring O(n) space.
The helper function is_non_decreasing uses only constant extra space.
No additional data structures grow with the input size, so the overall space complexity is O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Using `<=` instead of `<` when scanning for the minimum-sum pair (breaking the "leftmost" tie rule)

A very common mistake is writing the comparison as:

if min_sum >= current_sum:   # WRONG
    min_sum = current_sum
    min_index = i

The problem explicitly states that when several adjacent pairs share the same minimum sum, you must pick the leftmost one. With >=, every time a later pair ties the current minimum, the code overwrites min_index with the larger (rightward) index, so you end up merging the rightmost minimum-sum pair instead of the leftmost.

Why it matters: Merging a different pair changes the resulting array, which can change which pairs are merged in subsequent steps, ultimately producing a wrong operation count.

Solution: Use a strict comparison (>) so a tie never triggers an update. The first time the minimum value is seen, min_index is locked in, and equal sums encountered later are ignored — exactly preserving the leftmost choice.

if min_sum > current_sum:    # CORRECT — keeps the leftmost pair on ties
    min_sum = current_sum
    min_index = i

Pitfall 2: Forgetting the edge case of an array with fewer than 2 elements

The initialization min_sum = arr[0] + arr[1] assumes the array has at least two elements. If nums is empty or has a single element, arr[1] raises an IndexError.

In practice this code is safe because is_non_decreasing returns True for arrays of length 0 or 1 (the loop body never runs), so the while body is never entered. However, if you refactor the loop or reorder the logic, this hidden dependency can resurface.

Solution: Guard the minimum-sum initialization, or rely explicitly on the non-decreasing check running first:

while not is_non_decreasing(arr):
    # At this point len(arr) >= 2 is guaranteed, but make it explicit if refactoring:
    if len(arr) < 2:
        break
    min_index = 0
    min_sum = arr[0] + arr[1]
    ...

Pitfall 3: Re-checking `is_non_decreasing` over the whole array every iteration (performance trap)

Calling is_non_decreasing(arr) from scratch on each loop iteration adds an extra O(n) scan per operation. For the given constraints this O(n^2) total is acceptable, but on large inputs it becomes a bottleneck. A common pitfall is assuming this simulation scales to very large n.

Solution: For larger inputs, track the number of "violations" (indices where arr[i] < arr[i-1]) incrementally and maintain the minimum-sum pair with a heap, updating only the local neighborhood affected by each merge. This reduces the complexity toward O(n log n):

import heapq

class Solution:
    def minimumPairRemoval(self, nums: List[int]) -> int:
        n = len(nums)
        # Doubly-linked-list style via next/prev pointers + lazy heap.
        # Maintain a count of descending adjacent pairs (violations).
        # Each merge only affects the merged node and its two neighbors,
        # so update the violation count and push new pair sums locally.
        ...

The key insight is that a merge at index k only changes the pairs (k-1, k) and (k, k+1) — everything else is untouched — so neither the violation count nor the candidate pair sums need a full rescan.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: