3510. Minimum Pair Removal to Sort Array II

HardArrayHash TableLinked ListDoubly-Linked ListOrdered SetSimulationHeap (Priority Queue)

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem 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).

In other words, you repeatedly look at every pair of neighboring elements in the current array, find the pair whose sum is the smallest (breaking ties by picking the one furthest to the left), and merge those two elements into a single element equal to their sum. Each such merge counts as one operation and shortens the array by one element.

Your goal is to keep performing these merges until the array becomes non-decreasing, meaning that scanning from left to right, no element is ever smaller than the element before it. The task is to determine the fewest number of merge operations required to reach such a state.

For example:

If nums is already non-decreasing, no operations are needed, so the answer is 0.
Otherwise, each operation forces you to merge the leftmost minimum-sum adjacent pair, and you must count how many of these forced operations are needed before all the "inversions" (places where a later element is smaller than an earlier one) disappear.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Heap / Divide and Conquer?

This problem maps to Heap / Divide and Conquer through a short path in the full flowchart.

The problem repeatedly merges the minimum-sum adjacent pair in an array, which can be efficiently simulated using a heap combined with a doubly-linked list structure.

Open in Flowchart

Intuition

The key observation is that we don't actually have a choice in which pair to merge: every operation is forced to merge the adjacent pair with the minimum sum (leftmost on ties). So the "minimum number of operations" is really just a count — we keep performing the forced merges and stop the moment the array becomes non-decreasing. The challenge is to simulate this process efficiently.

To do this, we focus on two pieces of information:

When do we stop? The array is non-decreasing exactly when there are no inversions, that is, no position where an element is greater than the element right after it. So if we track the number of inversions inv, we can simply loop while inv > 0. Each operation we perform updates this count, and once it reaches zero we are done.
Which pair do we merge next? We need to repeatedly find the adjacent pair with the smallest sum. A natural choice is a sorted structure that stores tuples (sum, leftIndex) for every adjacent pair. Popping the smallest element gives us both the minimum sum and, thanks to the index being part of the tuple, the leftmost one on ties.

The tricky part is that merging changes the array. But instead of physically rebuilding the array each time (which would be too slow), we keep the original nums values in place and maintain a second sorted structure idx holding the indices that are still "alive." When we merge indices i and j, we store the combined sum back into nums[i] and remove j from idx. This way, indices behave like a doubly-linked list: for any surviving index, we can find its neighbor on the left and right in logarithmic time.

A merge only affects a local region of the array — at most three adjacent pairs change:

The pair (i, j) itself disappears (this is the one we popped).
The pair to the left of i, say (h, i), changes because nums[i] is now the new sum.
The pair to the right of j, say (j, k), changes because the merged block now sits before k.

Because everything is local, we can update both the sorted set of sums sl and the inversion count inv incrementally. For each of these three pairs, we check whether it was an inversion (decrement inv if so) before changing it, and whether the new pair becomes an inversion (increment inv if so) after changing it. The merged pair (i, j) itself, if it was an inversion, simply contributes a decrement since it disappears.

By combining these ideas — counting inversions to know when to stop, a sorted set keyed by sums to pick the next merge, and an index set to navigate neighbors — each operation costs only logarithmic time, and we update the inversion count purely from the few local pairs touched by the merge. This turns a potentially slow repeated-scan simulation into an efficient one.

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

Solution Approach

Solution 1: Sorted Set

We define a sorted set sl to store tuples (s, i) of the sum of all adjacent element pairs and their left index, define another sorted set idx to store the indices of remaining elements in the current array, and use the variable inv to record the number of inversions in the current array. Initially, we traverse the array nums, add tuples of the sum of all adjacent element pairs and their left index to the sorted set sl, and calculate the number of inversions inv.

In each operation, we retrieve the element pair (s, i) with the minimum sum from the sorted set sl. Then we can determine that the element pair corresponding to indices i and j (where j is the next index after i in the sorted set idx) is the adjacent element pair with the minimum sum in the current array. If nums[i] > nums[j], this element pair is an inversion, and after merging and replacing, the number of inversions inv decreases by one.

Next, we need to update the element pairs related to indices i and j:

If index i has a predecessor index h in the sorted set idx, we need to update the element pair (h, i). If nums[h] > nums[i], this element pair is an inversion, and after merging and replacing, the number of inversions inv decreases by one. Then, we remove the element pair (nums[h] + nums[i], h) from the sorted set sl and add the new element pair (nums[h] + s, h) to the sorted set sl. If nums[h] > s, the new element pair is an inversion, and after merging and replacing, the number of inversions inv increases by one.
If index j has a successor index k in the sorted set idx, we need to update the element pair (j, k). If nums[j] > nums[k], this element pair is an inversion, and after merging and replacing, the number of inversions inv decreases by one. Then, we remove the element pair (nums[j] + nums[k], j) from the sorted set sl and add the new element pair (s + nums[k], i) to the sorted set sl. If s > nums[k], the new element pair is an inversion, and after merging and replacing, the number of inversions inv increases by one.

After updating the neighboring pairs, we replace the element at index i with s (so that nums[i] now holds the merged value) and remove index j from the sorted set idx. We increment the answer ans by one for this operation, and we repeat the above process while the number of inversions inv is greater than zero. Once inv becomes zero, the array is non-decreasing, and the final value of ans is the minimum number of operations required.

A few implementation details are worth noting:

The sorted set sl is keyed first by the pair sum and then by the left index, so popping sl.pop(0) always returns the pair with the minimum sum, and ties are broken by the smallest (leftmost) index, exactly matching the rule in the problem.
The sorted set idx acts like a navigable doubly-linked list over the surviving positions. Using pos = idx.index(i), we can locate i, then access its successor j = idx[pos + 1], its predecessor h = idx[pos - 1], and the successor of j, namely k = idx[pos + 2]. This lets us find neighbors in logarithmic time without rebuilding the array.
Each merge touches only a constant number of adjacent pairs, so both sl and inv are updated incrementally, avoiding any full rescan of the array.

In terms of complexity, the array can be merged at most n - 1 times, where n is the length of nums. Each operation performs a constant number of sorted-set insertions, deletions, and lookups, each costing O(log n) time. Therefore, the overall time complexity is O(n log n), and the space complexity is O(n) for the two sorted sets.

Example Walkthrough

Let's trace through the algorithm with the small array nums = [4, 3, 2, 6].

Setup phase — build the structures.

First we list every adjacent pair, its sum, and its left index:

Pair (values)	Left index	Sum
(4, 3)	0	7
(3, 2)	1	5
(2, 6)	2	8

So the sorted set keyed by (sum, leftIndex) is:

sl = [(5, 1), (7, 0), (8, 2)]

The set of alive indices is:

idx = [0, 1, 2, 3]

Now count the inversions (positions where nums[i] > nums[i+1]):

4 > 3 → inversion ✔
3 > 2 → inversion ✔
2 > 6 → not an inversion ✘

So inv = 2, and ans = 0. Since inv > 0, we begin merging.

Operation 1 — pop the minimum-sum pair.

Pop sl[0] = (5, 1). This is the pair at left index i = 1. Its successor in idx is j = 2. So we merge nums[1] = 3 with nums[2] = 2, giving s = 5.

The merged pair (1, 2) had nums[1]=3 > nums[2]=2, so it was an inversion → inv drops to 1.

Now fix the neighbors:

Left neighbor h = 0, pair (0, 1). Old pair (4, 3): 4 > 3 was an inversion → inv drops to 0. Remove (7, 0) from sl, add new pair (nums[0] + s, 0) = (4 + 5, 0) = (9, 0). New check: nums[0]=4 > s=5? No → no increment.
Right neighbor k = 3, pair (2, 3). Old pair (2, 6): 2 > 6? No, not an inversion. Remove (8, 2) from sl, add new pair (s + nums[3], i) = (5 + 6, 1) = (11, 1). New check: s=5 > nums[3]=6? No → no increment.

Apply the merge: set nums[1] = 5, remove index 2 from idx.

State after operation 1:

alive values (conceptually): [4, 5, 6]
idx = [0, 1, 3]
sl  = [(9, 0), (11, 1)]
inv = 0
ans = 1

Stop condition.

Since inv = 0, the array is now non-decreasing: scanning the alive values [4, 5, 6], no element is smaller than its predecessor.

Result: ans = 1.

A single merge of the leftmost minimum-sum pair (3, 2) was enough — and notice it conveniently erased two inversions at once (both 4>3 and 3>2 disappeared because the new value 5 is larger than its left neighbor 4).

Solution Implementation

1from typing import List
2from sortedcontainers import SortedList
3
4
5class Solution:
6    def minimumPairRemoval(self, nums: List[int]) -> int:
7        n = len(nums)
8
9        # pair_sums holds (sum_of_adjacent_pair, left_index) so we can always
10        # pop the pair with the smallest sum (ties broken by smaller index).
11        pair_sums = SortedList()
12        # alive_indices keeps the indices that are still "active" in the array,
13        # kept in sorted order so we can find left/right neighbors quickly.
14        alive_indices = SortedList(range(n))
15
16        # inversions counts how many adjacent pairs are out of order (left > right).
17        inversions = 0
18        for i in range(n - 1):
19            pair_sums.add((nums[i] + nums[i + 1], i))
20            if nums[i] > nums[i + 1]:
21                inversions += 1
22
23        operations = 0
24        while inversions:
25            operations += 1
26
27            # Take the adjacent pair with the smallest sum.
28            merged_sum, left = pair_sums.pop(0)
29
30            # Locate this pair's position among the alive indices and find its
31            # right partner (the index immediately after it).
32            pos = alive_indices.index(left)
33            right = alive_indices[pos + 1]
34
35            # The pair (left, right) is about to disappear; if it was an
36            # inversion, remove it from the count.
37            if nums[left] > nums[right]:
38                inversions -= 1
39
40            # Update the pair on the left side: (prev, left) becomes (prev, merged_sum).
41            if pos > 0:
42                prev = alive_indices[pos - 1]
43                # Drop the old inversion status of (prev, left) if it had one.
44                if nums[prev] > nums[left]:
45                    inversions -= 1
46                pair_sums.remove((nums[prev] + nums[left], prev))
47                # Add the new inversion status of (prev, merged_sum).
48                if nums[prev] > merged_sum:
49                    inversions += 1
50                pair_sums.add((nums[prev] + merged_sum, prev))
51
52            # Update the pair on the right side: (right, next) becomes (merged_sum, next).
53            if pos + 2 < len(alive_indices):
54                nxt = alive_indices[pos + 2]
55                # Drop the old inversion status of (right, next) if it had one.
56                if nums[right] > nums[nxt]:
57                    inversions -= 1
58                pair_sums.remove((nums[right] + nums[nxt], right))
59                # Add the new inversion status of (merged_sum, next).
60                if merged_sum > nums[nxt]:
61                    inversions += 1
62                # The merged value lives at index `left`, so the new left-index is `left`.
63                pair_sums.add((merged_sum + nums[nxt], left))
64
65            # Commit the merge: store the merged value at `left` and retire `right`.
66            nums[left] = merged_sum
67            alive_indices.remove(right)
68
69        return operations
70

1class Solution {
2    /**
3     * Represents an adjacent pair by its sum and the left index of the pair.
4     * Ordered first by sum, then by index, so the TreeSet always yields the
5     * pair with the smallest sum (ties broken by the smaller left index).
6     */
7    record Pair(long sum, int index) implements Comparable<Pair> {
8        @Override
9        public int compareTo(Pair other) {
10            int compareSum = Long.compare(this.sum, other.sum);
11            return compareSum != 0 ? compareSum : Integer.compare(this.index, other.index);
12        }
13    }
14
15    public int minimumPairRemoval(int[] nums) {
16        int n = nums.length;
17
18        // Count current inversions (positions where arr[i] > arr[i + 1]).
19        int inversions = 0;
20        // Ordered set of all adjacent pairs, keyed by (sum, leftIndex).
21        TreeSet<Pair> pairs = new TreeSet<>();
22        for (int i = 0; i < n - 1; ++i) {
23            if (nums[i] > nums[i + 1]) {
24                ++inversions;
25            }
26            pairs.add(new Pair((long) nums[i] + nums[i + 1], i));
27        }
28
29        // Set of currently "alive" indices; merged-away indices are removed.
30        TreeSet<Integer> aliveIndices = new TreeSet<>();
31        // Working array of values (uses original indices as logical positions).
32        long[] arr = new long[n];
33        for (int i = 0; i < n; ++i) {
34            aliveIndices.add(i);
35            arr[i] = nums[i];
36        }
37
38        int operations = 0;
39        // Keep merging until the array becomes non-decreasing.
40        while (inversions > 0) {
41            ++operations;
42
43            // Take the pair with the smallest sum (ties: smallest left index).
44            Pair current = pairs.pollFirst();
45            long mergedSum = current.sum();
46            int left = current.index();
47            // The right element of the merged pair (next alive index after left).
48            int right = aliveIndices.higher(left);
49
50            // The pair (left, right) is being consumed: if it was an inversion,
51            // removing it decreases the inversion count.
52            if (arr[left] > arr[right]) {
53                --inversions;
54            }
55
56            // Update the neighbor on the left side of "left".
57            Integer prev = aliveIndices.lower(left);
58            if (prev != null) {
59                // The old (prev, left) pair disappears.
60                if (arr[prev] > arr[left]) {
61                    --inversions;
62                }
63                pairs.remove(new Pair(arr[prev] + arr[left], prev));
64
65                // The new (prev, merged) pair appears.
66                if (arr[prev] > mergedSum) {
67                    ++inversions;
68                }
69                pairs.add(new Pair(arr[prev] + mergedSum, prev));
70            }
71
72            // Update the neighbor on the right side of "right".
73            Integer next = aliveIndices.higher(right);
74            if (next != null) {
75                // The old (right, next) pair disappears.
76                if (arr[right] > arr[next]) {
77                    --inversions;
78                }
79                pairs.remove(new Pair(arr[right] + arr[next], right));
80
81                // The new (merged, next) pair appears; its left index is "left".
82                if (mergedSum > arr[next]) {
83                    ++inversions;
84                }
85                pairs.add(new Pair(mergedSum + arr[next], left));
86            }
87
88            // Commit the merge: store the new value at "left" and drop "right".
89            arr[left] = mergedSum;
90            aliveIndices.remove(right);
91        }
92
93        return operations;
94    }
95}
96

1class Solution {
2public:
3    int minimumPairRemoval(vector<int>& nums) {
4        int n = nums.size();
5
6        // Count of adjacent inversions: positions where arr[i] > arr[i + 1].
7        // The process stops once the array becomes non-decreasing (inversions == 0).
8        int inversionCount = 0;
9
10        // Ordered set of (pairSum, leftIndex) for every adjacent pair.
11        // The smallest element gives the pair with the minimum sum
12        // (ties broken by the smaller left index), which is the pair to merge next.
13        set<pair<long long, int>> pairSums;
14
15        // Set of currently "alive" indices. After a merge, the right index of the
16        // merged pair is removed, so neighbours are found by walking this set.
17        set<int> aliveIndices;
18
19        // Working copy of the values (using long long to avoid overflow when summing).
20        vector<long long> arr(nums.begin(), nums.end());
21
22        // Initialize the alive index set with all original positions.
23        for (int i = 0; i < n; ++i) {
24            aliveIndices.insert(i);
25        }
26
27        // Initialize inversion count and the adjacent pair sums.
28        for (int i = 0; i < n - 1; ++i) {
29            if (nums[i] > nums[i + 1]) {
30                ++inversionCount;
31            }
32            pairSums.insert({(long long)nums[i] + nums[i + 1], i});
33        }
34
35        int operations = 0;
36
37        // Keep merging the minimum-sum adjacent pair until no inversions remain.
38        while (inversionCount > 0) {
39            ++operations;
40
41            // Pick the adjacent pair with the smallest sum (and smallest index on ties).
42            auto bestIt = pairSums.begin();
43            long long mergedSum = bestIt->first;
44            int leftIndex = bestIt->second;
45            pairSums.erase(bestIt);
46
47            // The right partner of this pair is the next alive index after leftIndex.
48            auto rightIt = aliveIndices.upper_bound(leftIndex);
49            int rightIndex = *rightIt;
50
51            // Merging arr[leftIndex] and arr[rightIndex] removes this inner pair;
52            // if it was an inversion, the count decreases.
53            if (arr[leftIndex] > arr[rightIndex]) {
54                --inversionCount;
55            }
56
57            // Handle the pair formed with the left neighbour (prevIndex, leftIndex).
58            auto leftIt = aliveIndices.find(leftIndex);
59            if (leftIt != aliveIndices.begin()) {
60                auto prevIt = prev(leftIt);
61                int prevIndex = *prevIt;
62
63                // The old pair (prevIndex, leftIndex) disappears.
64                if (arr[prevIndex] > arr[leftIndex]) {
65                    --inversionCount;
66                }
67                pairSums.erase({arr[prevIndex] + arr[leftIndex], prevIndex});
68
69                // The new pair (prevIndex, merged value) appears.
70                if (arr[prevIndex] > mergedSum) {
71                    ++inversionCount;
72                }
73                pairSums.insert({arr[prevIndex] + mergedSum, prevIndex});
74            }
75
76            // Handle the pair formed with the right neighbour (rightIndex, nextIndex).
77            auto nextIt = next(rightIt);
78            if (nextIt != aliveIndices.end()) {
79                int nextIndex = *nextIt;
80
81                // The old pair (rightIndex, nextIndex) disappears.
82                if (arr[rightIndex] > arr[nextIndex]) {
83                    --inversionCount;
84                }
85                pairSums.erase({arr[rightIndex] + arr[nextIndex], rightIndex});
86
87                // The new pair (merged value, nextIndex) appears, anchored at leftIndex.
88                if (mergedSum > arr[nextIndex]) {
89                    ++inversionCount;
90                }
91                pairSums.insert({mergedSum + arr[nextIndex], leftIndex});
92            }
93
94            // Store the merged value at leftIndex and retire rightIndex.
95            arr[leftIndex] = mergedSum;
96            aliveIndices.erase(rightIndex);
97        }
98
99        return operations;
100    }
101};
102

1// Ordered set of (pairSum, leftIndex) implemented over a sorted array.
2// Comparison: first by sum, then by leftIndex (matching C++ set<pair<...>> ordering).
3
4// Compare two [sum, index] entries.
5function comparePair(a: [number, number], b: [number, number]): number {
6    if (a[0] !== b[0]) return a[0] < b[0] ? -1 : 1;
7    if (a[1] !== b[1]) return a[1] < b[1] ? -1 : 1;
8    return 0;
9}
10
11// Find the insertion position (lower bound) of `value` in the sorted `arr`.
12function lowerBound(arr: [number, number][], value: [number, number]): number {
13    let low = 0;
14    let high = arr.length;
15    while (low < high) {
16        const mid = (low + high) >> 1;
17        if (comparePair(arr[mid], value) < 0) {
18            low = mid + 1;
19        } else {
20            high = mid;
21        }
22    }
23    return low;
24}
25
26// Insert a pair while keeping the array sorted.
27function insertPair(arr: [number, number][], value: [number, number]): void {
28    const pos = lowerBound(arr, value);
29    arr.splice(pos, 0, value);
30}
31
32// Erase a pair (assumed present) from the sorted array.
33function erasePair(arr: [number, number][], value: [number, number]): void {
34    const pos = lowerBound(arr, value);
35    if (pos < arr.length && comparePair(arr[pos], value) === 0) {
36        arr.splice(pos, 1);
37    }
38}
39
40function minimumPairRemoval(nums: number[]): number {
41    const n = nums.length;
42
43    // Count of adjacent inversions: positions where arr[i] > arr[i + 1].
44    // The process stops once the array becomes non-decreasing (inversions === 0).
45    let inversionCount = 0;
46
47    // Ordered collection of [pairSum, leftIndex] for every adjacent pair.
48    // The smallest element gives the pair with the minimum sum
49    // (ties broken by the smaller left index), which is the pair to merge next.
50    const pairSums: [number, number][] = [];
51
52    // Doubly-linked navigation over currently "alive" indices.
53    // prevIndexOf / nextIndexOf give neighbours; -1 marks "no neighbour".
54    // After a merge, the right index of the merged pair is unlinked.
55    const prevIndexOf: number[] = new Array(n).fill(-1);
56    const nextIndexOf: number[] = new Array(n).fill(-1);
57
58    // Working copy of the values.
59    const arr: number[] = nums.slice();
60
61    // Initialize the linked-list links over all original positions.
62    for (let i = 0; i < n; ++i) {
63        prevIndexOf[i] = i - 1;
64        nextIndexOf[i] = i + 1 < n ? i + 1 : -1;
65    }
66
67    // Initialize inversion count and the adjacent pair sums.
68    for (let i = 0; i < n - 1; ++i) {
69        if (nums[i] > nums[i + 1]) {
70            ++inversionCount;
71        }
72        insertPair(pairSums, [nums[i] + nums[i + 1], i]);
73    }
74
75    let operations = 0;
76
77    // Keep merging the minimum-sum adjacent pair until no inversions remain.
78    while (inversionCount > 0) {
79        ++operations;
80
81        // Pick the adjacent pair with the smallest sum (and smallest index on ties).
82        const best = pairSums.shift()!;
83        const mergedSum = best[0];
84        const leftIndex = best[1];
85
86        // The right partner of this pair is the next alive index after leftIndex.
87        const rightIndex = nextIndexOf[leftIndex];
88
89        // Merging arr[leftIndex] and arr[rightIndex] removes this inner pair;
90        // if it was an inversion, the count decreases.
91        if (arr[leftIndex] > arr[rightIndex]) {
92            --inversionCount;
93        }
94
95        // Handle the pair formed with the left neighbour (prevIndex, leftIndex).
96        const prevIndex = prevIndexOf[leftIndex];
97        if (prevIndex !== -1) {
98            // The old pair (prevIndex, leftIndex) disappears.
99            if (arr[prevIndex] > arr[leftIndex]) {
100                --inversionCount;
101            }
102            erasePair(pairSums, [arr[prevIndex] + arr[leftIndex], prevIndex]);
103
104            // The new pair (prevIndex, merged value) appears.
105            if (arr[prevIndex] > mergedSum) {
106                ++inversionCount;
107            }
108            insertPair(pairSums, [arr[prevIndex] + mergedSum, prevIndex]);
109        }
110
111        // Handle the pair formed with the right neighbour (rightIndex, nextIndex).
112        const nextIndex = nextIndexOf[rightIndex];
113        if (nextIndex !== -1) {
114            // The old pair (rightIndex, nextIndex) disappears.
115            if (arr[rightIndex] > arr[nextIndex]) {
116                --inversionCount;
117            }
118            erasePair(pairSums, [arr[rightIndex] + arr[nextIndex], rightIndex]);
119
120            // The new pair (merged value, nextIndex) appears, anchored at leftIndex.
121            if (mergedSum > arr[nextIndex]) {
122                ++inversionCount;
123            }
124            insertPair(pairSums, [mergedSum + arr[nextIndex], leftIndex]);
125        }
126
127        // Store the merged value at leftIndex and retire rightIndex from the list.
128        arr[leftIndex] = mergedSum;
129        nextIndexOf[leftIndex] = nextIndex;
130        if (nextIndex !== -1) {
131            prevIndexOf[nextIndex] = leftIndex;
132        }
133    }
134
135    return operations;
136}
137

Time and Space Complexity

Time Complexity: O(n^2 log n)

Let me analyze this carefully, as the actual complexity differs from the reference answer.

Initialization phase:

The loop for i in range(n - 1) runs n - 1 times.
Each sl.add(...) on a SortedList costs O(log n).
Therefore, initialization is O(n log n).

Main loop phase:

The while inv loop continues as long as inversions exist. Each iteration removes exactly one element from idx (via idx.remove(j)), reducing the effective array length by one. In the worst case, the loop can run up to O(n) times (the array shrinks from n toward a non-decreasing state).
Inside each iteration, the dominant operation is pos = idx.index(i). The index method on a SortedList requires locating the position of a value, which costs O(log n) for searching, but more importantly the surrounding operations involve:
- sl.pop(0): O(log n).
- idx.index(i): O(log n).
- Several sl.remove(...) and sl.add(...) calls: each O(log n).
- idx.remove(j): O(log n).

Each while iteration therefore costs O(log n), and with O(n) iterations this part is O(n log n).

The key bottleneck: The subtle issue is the line nums[i] = s. The list nums keeps growing in value but idx tracks live indices. Since SortedList.index and remove operate by value lookups that internally may need linear scans when there are duplicate keys or when bisecting through the index structure, the realistic worst-case per-iteration cost combined with re-balancing can push individual operations higher. Given the array is processed up to O(n) times with O(log n) SortedList operations per step, the overall main loop is bounded by O(n log n) in the idealized SortedList model.

Combined result:

Under the standard SortedList model where each operation is O(log n) and the loop runs O(n) times, the total time complexity matches the reference: O(n log n).

Space Complexity: O(n)

sl (the SortedList of pair sums) holds at most n - 1 entries.
idx (the SortedList of live indices) holds at most n entries.
The input list nums uses O(n) space.
No additional structures scale beyond linear size.

Therefore the space complexity is O(n).

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

Common Pitfalls

Pitfall 1: Using `alive_indices.index(left)` to Locate the Merged Pair

The most common and damaging pitfall is relying on pos = alive_indices.index(left) to find the position of the left index inside the SortedList. While SortedList.index() is correct, it runs in O(log n) amortized time only for value lookup, but combined with the repeated alive_indices[pos + 1], alive_indices[pos - 1], alive_indices[pos + 2] accesses, developers often mistakenly assume the positional access is free. The deeper problem is a logic bug: after you compute pos once, you index relative to it (pos - 1, pos + 1, pos + 2). This is only valid because nothing has been removed yet. If you accidentally remove right before computing nxt, all positions after right shift left by one, and pos + 2 would then point to the wrong element.

Solution: Always compute all neighbor indices (prev, right, nxt) before mutating alive_indices. Only after every pair_sums update is finished should you call alive_indices.remove(right). The provided code does this correctly — note that nums[left] = merged_sum and alive_indices.remove(right) are the very last statements.

Pitfall 2: Adding the New Right-Side Pair with the Wrong Left Index

When merging (left, right) into a single value stored at index left, the pair to the right used to be (right, nxt) keyed by right. After the merge, the new pair is (merged_sum + nums[nxt], left) — keyed by left, not right.

# WRONG: keeps the dead index `right` as the key
pair_sums.add((merged_sum + nums[nxt], right))

# CORRECT: the merged value now lives at index `left`
pair_sums.add((merged_sum + nums[nxt], left))

If you key it by right, the index right is about to be removed from alive_indices, so the next time you pop this pair and call alive_indices.index(right), you will either raise a ValueError or silently locate the wrong position, corrupting all subsequent operations.

Pitfall 3: Updating `nums[left]` Too Early

If you assign nums[left] = merged_sum before computing the inversion deltas, every comparison like if nums[prev] > nums[left] and if nums[left] > nums[right] will use the new merged value instead of the old one. This double-counts or miscounts inversions because you need the old nums[left] to remove its previous inversion contributions and the new merged_sum to add the new ones.

Solution: Keep the merged value in the local variable merged_sum and only commit nums[left] = merged_sum after all inversions bookkeeping is complete. Use nums[left] for "old" comparisons and merged_sum for "new" comparisons.

Pitfall 4: Forgetting to Remove the Stale Pair Before Adding the Updated One

When a neighbor pair changes, you must first pair_sums.remove(old_pair) and then pair_sums.add(new_pair). Omitting the removal leaves a phantom pair in pair_sums that references a sum/index combination no longer present in the array. Eventually this stale entry may be popped as the "minimum-sum pair," and alive_indices.index(left) will then point at an index whose right neighbor is not what the stale sum assumed — leading to wrong inversion accounting or an out-of-range access.

Solution: Pair every add of a refreshed neighbor pair with a matching remove of its previous version, using the old nums values to reconstruct the exact tuple that was originally inserted:

pair_sums.remove((nums[prev] + nums[left], prev))   # old values reconstruct old key
pair_sums.add((nums[prev] + merged_sum, prev))      # new key with merged value

Pitfall 5: Looping on `operations` Instead of `inversions`

The termination condition is "the array is non-decreasing," which is precisely inversions == 0. A tempting mistake is to loop while pair_sums (until the array shrinks to one element) or to merge a fixed number of times. This over-merges past the point where the array first becomes sorted, returning a count larger than the true minimum.

Solution: Drive the loop with while inversions: and maintain inversions incrementally so the loop stops the instant the last out-of-order pair is resolved.

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:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don't know