Watch 10 video solutions for Minimum Pair Removal to Sort Array II, a hard level problem involving Array, Hash Table, Linked List. This walkthrough by codestorywithMIK has 14,125 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |