Skip to main content
Talentd

Minimum Pair Removal to Sort Array II - Solution & Explanation

HardArrayHash TableLinked ListHeap (Priority Queue)15 min readAsked at: Amazon, Microsoft, Google
Practice this problem

Problem Statement

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

 

Example 1:

Input: nums = [5,2,3,1]

Output: 2

Explanation:

  • The pair (3,1) has the minimum sum of 4. After replacement, nums = [5,2,4].
  • The pair (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] <= 109

Approach Overview

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

Solution

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:

  1. 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.

  2. 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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 ListO(n log n)O(n)General optimal solution when many removals occur and neighbor relationships change dynamically.
Heap / Priority Queue SimulationO(n log n)O(n)Alternative implementation where problematic pairs are processed using a priority queue instead of an ordered set.

Video Solution

Minimum Pair Removal to Sort Array II | Detailed Explanation | Leetcode 3510 | codestorywithMIK • codestorywithMIK • 14,542 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Pair Removal to Sort Array II easy or hard?
Minimum Pair Removal to Sort Array II is classified as a Hard problem. The difficulty comes from managing dynamically changing neighbors and avoiding repeated full scans of the array while keeping operations efficient.
Minimum Pair Removal to Sort Array II Python/Java solution
Typical implementations maintain arrays for previous and next indices to simulate a doubly linked list and store problematic pairs in a TreeSet, heap, or sorted container. Python solutions often use SortedList or heap-based approaches, while Java and C++ commonly use TreeSet or priority_queue.
How to solve Minimum Pair Removal to Sort Array II in O(n)?
A strict O(n) solution is generally not feasible because maintaining dynamically changing neighbor relationships requires ordered lookups. Most implementations rely on ordered sets or priority queues, leading to O(n log n) complexity.
What is the best approach for Minimum Pair Removal to Sort Array II?
The most efficient method uses an ordered set combined with a doubly linked list to simulate pair removals. Track adjacent pairs that violate sorted order and process them while dynamically updating neighbors. Each update costs O(log n), producing an overall time complexity of O(n log n).
Is Minimum Pair Removal to Sort Array II asked at Google/Amazon/Meta?
Problems involving dynamic neighbor updates, ordered sets, and simulation patterns frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of array simulation with priority structures are common in senior-level algorithm rounds.
What data structure is used in Minimum Pair Removal to Sort Array II?
The main structures are a doubly linked list to maintain active neighbors and an ordered set (or priority queue) to track invalid adjacent pairs. This combination enables efficient deletions and fast retrieval of the next pair to process.
What is the time complexity of Minimum Pair Removal to Sort Array II?
The optimal algorithm runs in O(n log n) time and O(n) space. Ordered set operations such as insert and delete take O(log n), and each pair is processed at most once during the simulation.

Ready to solve this problem?

Practice Minimum Pair Removal to Sort Array II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays