Skip to main content
Talentd

Minimum Pair Removal to Sort Array I - Solution & Explanation

EasyArrayHash TableLinked ListHeap (Priority Queue)8 min readAsked at: Amazon, Microsoft, Meta +2
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 <= 50
  • -1000 <= nums[i] <= 1000

Approach Overview

Problem Overview: You are given an array and repeatedly remove pairs of adjacent elements following a specific rule until the array becomes non‑decreasing. The task is to compute the minimum number of pair removals required to make the remaining sequence sorted.

Approach 1: Brute Force Simulation (O(n^2) time, O(1) space)

The straightforward approach repeatedly scans the array to locate candidate adjacent pairs, removes the required pair, and rebuilds the array. After each removal you check whether the array is already non‑decreasing. Because each removal requires shifting elements and rescanning the array, the total cost grows quickly. This approach is useful to understand the mechanics of the operation but becomes inefficient when the array is large.

Approach 2: Heap + Doubly Linked List Simulation (O(n log n) time, O(n) space)

A more efficient solution treats the array as a dynamic structure where adjacent pairs are updated after each removal. Store all adjacent pairs in a min‑heap keyed by their pair value (for example the pair sum). Each heap entry also tracks the indices of the two elements. To support efficient deletions and neighbor updates, represent the array using a doubly‑linked list. When a pair is removed, update the neighboring nodes and push the newly formed adjacent pair into the heap.

Since removed elements invalidate some heap entries, lazy deletion is used: when a pair is popped from the heap, verify that both nodes are still active in the linked structure. If valid, remove the pair and connect its neighbors. This keeps pair updates local and avoids rescanning the entire array.

The heap ensures the next candidate pair is selected in O(log n) time, while the linked list handles removals and neighbor connections in constant time. The algorithm simulates the process efficiently and maintains the correct ordering constraints as the structure evolves. Concepts from heap (priority queue), array, and simulation are combined to maintain dynamic adjacency relationships.

Recommended for interviews: The heap + doubly linked list simulation is the expected approach. It demonstrates control over dynamic array updates, priority queues, and efficient neighbor maintenance. Starting with a brute force explanation shows you understand the process, while the optimized simulation shows practical problem‑solving skills.

Solution

We define a function is_non_decreasing(a) to determine whether the array a is a non-decreasing array.

We use a loop until the array arr becomes a non-decreasing array. In each iteration of the loop, we find the minimum sum of adjacent element pairs in the array arr and record the index k of the left element of that pair. Then, we replace the left element with the sum of the pair and remove the right element. Finally, we return the number of operations.

The time complexity is O(n^2), and the space complexity is O(n), where n is the length of the array.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SimulationO(n^2)O(1)Useful for understanding the process or very small arrays
Heap + Doubly Linked List SimulationO(n log n)O(n)General case where efficient pair selection and updates are required

Video Solution

Minimum Pair Removal to Sort Array I | Simple Explanation | Leetcode 3507 | codestorywithMIK • codestorywithMIK • 10,280 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Pair Removal to Sort Array I easy or hard?
The problem is classified as Easy, but the optimal implementation introduces concepts like heaps and linked list simulation. The core logic is straightforward once the dynamic adjacency updates are handled correctly.
Minimum Pair Removal to Sort Array I Python/Java solution
Python, Java, C++, Go, TypeScript, and Rust implementations follow the same idea: maintain adjacent pairs in a priority queue and update neighbors using a linked structure after each removal. Each language uses its standard priority queue and array or node representation.
How to solve Minimum Pair Removal to Sort Array I in O(n)?
An exact O(n) approach is generally not practical because selecting the next pair requires ordering candidates by priority. Using a heap introduces the O(log n) factor. The closest practical solution uses a priority queue with a doubly linked list, resulting in O(n log n) time.
What is the best approach for Minimum Pair Removal to Sort Array I?
The most efficient solution uses simulation with a min‑heap and a doubly linked list. The heap quickly selects the next candidate adjacent pair, while the linked list allows constant‑time removals and neighbor updates. This combination keeps the total complexity around O(n log n) with O(n) space.
Is Minimum Pair Removal to Sort Array I asked at Google/Amazon/Meta?
Problems that combine heaps, simulation, and dynamic adjacency structures appear frequently in interviews at companies like Amazon, Google, and Meta. Variants involving priority queues and linked list updates are common because they test data structure integration and careful implementation.
What data structure is used in Minimum Pair Removal to Sort Array I?
The typical solution uses a min‑heap (priority queue) to choose the next pair efficiently and a doubly linked list to manage element removals and neighbor updates. Arrays track node status, and lazy deletion handles outdated heap entries.
What is the time complexity of Minimum Pair Removal to Sort Array I?
The optimized simulation runs in O(n log n) time because each pair insertion or extraction from the priority queue costs O(log n). Every element participates in a limited number of updates, so the total heap operations remain proportional to the array size. Space complexity is O(n).

Ready to solve this problem?

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

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays