Given an array nums, you can perform the following operation any number of times:
nums. If multiple such pairs exist, choose the leftmost one.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:
(3,1) has the minimum sum of 4. After replacement, nums = [5,2,4].(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] <= 109Problem Overview: You are given an array and repeatedly remove adjacent pairs until the remaining elements form a non‑decreasing array. Each removal changes which elements become neighbors, so the challenge is choosing the removal order that minimizes operations.
Approach 1: Naive Simulation (O(n^2) time, O(n) space)
A straightforward idea is to repeatedly scan the array and detect positions where the sorted order is violated (nums[i] > nums[i+1]). When such a pair appears, remove it and rebuild the array. Continue scanning until the array becomes non‑decreasing. This works because every removal potentially fixes one inversion, but each operation requires shifting elements or rebuilding the array structure. Since each scan costs O(n) and up to O(n) removals may occur, the total runtime becomes O(n^2). The approach is easy to reason about but too slow for large inputs.
Approach 2: Ordered Set + Doubly Linked List Simulation (O(n log n) time, O(n) space)
The optimal solution treats the array as a dynamic structure where neighbors change after each removal. Maintain a doubly linked list representation of indices so deletions happen in constant time. Next, track all "bad" adjacent pairs where nums[i] > nums[i+1]. Store these candidate pairs inside an ordered set (or priority structure) so you can always process the earliest problematic pair efficiently.
When you remove a pair, update the linked list by reconnecting the previous and next surviving indices. Only the neighbors around the removed segment can create new violations, so recheck those positions and update the ordered set accordingly. Each pair enters or leaves the set at most once, and each ordered‑set operation costs O(log n). This keeps the overall runtime at O(n log n) while maintaining accurate neighbor relationships throughout the simulation.
This approach combines ideas from array processing with dynamic adjacency tracking using a doubly linked list. The event-driven processing of invalid pairs resembles techniques used with heap / priority queue or ordered set structures.
Recommended for interviews: Interviewers expect the ordered-set simulation. The brute-force scan shows you understand the mechanics of the problem, but the optimized solution demonstrates skill with dynamic neighbor updates and event-driven processing. Recognizing that only nearby pairs change after a removal is the key insight that reduces repeated scanning.
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 (h, i) from the sorted set sl and add the new element pair (h, s) 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 (j, k) from the sorted set sl and add the new element pair (s, k) 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.
Next, we replace the element at index i with s and remove index j from the sorted set idx. We repeat the above process until the number of inversions inv becomes zero. Finally, the number of operations is the minimum number of operations required to make the array non-decreasing.
The time complexity is O(n log n), and the space complexity is O(n). Where n is the length of the array.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Simulation (Repeated Scans) | O(n^2) | O(n) | Good for understanding the mechanics of pair removals or when constraints are very small. |
| Ordered Set + Doubly Linked List | O(n log n) | O(n) | General optimal solution when many removals occur and neighbor relationships change dynamically. |
| Heap / Priority Queue Simulation | O(n log n) | O(n) | Alternative implementation where problematic pairs are processed using a priority queue instead of an ordered set. |
Minimum Pair Removal to Sort Array II | Detailed Explanation | Leetcode 3510 | codestorywithMIK • codestorywithMIK • 14,125 views views
Watch 9 more video solutions →Practice Minimum Pair Removal to Sort Array II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor