Minimum Pair Removal to Sort Array I solution and explanation
Google
9 more videos on this problem
Minimum Pair Removal to Sort Array I | Simple Explanation | Leetcode 3507 | codestorywithMIKcodestorywithMIK · 11:36 · 10K views
3507. Minimum Pair Removal to Sort Array I | Weekly Contest 444 | Arrays | LeetcodeRapid Syntax · 9:31 · 2K views
3507. Minimum Pair Removal to Sort Array I | Leetcode Daily - PythonLeetcode Daily · 8:52 · 1K views
Minimum Pair Removal to Sort Array | LeetCode 3507 | Beginner FriendlySanyam IIT Guwahati · 12:33 · 1K views
3507. Minimum Pair Removal to Sort Array I (Leetcode Easy)Programming Live with Larry · 8:59 · 865 views
Minimum Pair Removal to Sort Array I | LeetCode 3507 | SimulationcodeTips · 13:04 · 480 views
Daily Leetcode #2123: Jan 22, 2026 - 3507. Minimum Pair Removal to Sort Array ISProgramming Live with Larry · 12:50 · 429 views
Minimum Pair Removal to Sort Array I - Leetcode 3507 | Simulation Approach | Java - HindiKernel Queen 👑 · 7:50 · 357 views
Minimum Pair Removal to Sort Array I - Leetcode 3507 - PythonTim Huang · 5:41 · 349 views
Leetcode 3507. Minimum Pair Removal to Sort Array IExpertFunda · 10:35 · 176 views
The problem
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.
class Solution:
def minimumPairRemoval(self, nums: List[int]) -> int:
arr = nums[:]
ans = 0
def is_non_decreasing(a: List[int]) -> bool:
for i in range(1, len(a)):
if a[i] < a[i - 1]:
return False
return True
while not is_non_decreasing(arr):
k = 0
s = arr[0] + arr[1]
for i in range(1, len(arr) - 1):
t = arr[i] + arr[i + 1]
if s > t:
s = t
k = i
arr[k] = s
arr.pop(k + 1)
ans += 1
return ansclass Solution {
public int minimumPairRemoval(int[] nums) {
List<Integer> arr = new ArrayList<>();
for (int x : nums) {
arr.add(x);
}
int ans = 0;
while (!isNonDecreasing(arr)) {
int k = 0;
int s = arr.get(0) + arr.get(1);
for (int i = 1; i < arr.size() - 1; ++i) {
int t = arr.get(i) + arr.get(i + 1);
if (s > t) {
s = t;
k = i;
}
}
arr.set(k, s);
arr.remove(k + 1);
++ans;
}
return ans;
}
private boolean isNonDecreasing(List<Integer> arr) {
for (int i = 1; i < arr.size(); ++i) {
if (arr.get(i) < arr.get(i - 1)) {
return false;
}
}
return true;
}
}class Solution {
public:
int minimumPairRemoval(vector<int>& nums) {
vector<int> arr = nums;
int ans = 0;
while (!isNonDecreasing(arr)) {
int k = 0;
int s = arr[0] + arr[1];
for (int i = 1; i < arr.size() - 1; ++i) {
int t = arr[i] + arr[i + 1];
if (s > t) {
s = t;
k = i;
}
}
arr[k] = s;
arr.erase(arr.begin() + (k + 1));
++ans;
}
return ans;
}
private:
bool isNonDecreasing(const vector<int>& arr) {
for (int i = 1; i < (int) arr.size(); ++i) {
if (arr[i] < arr[i - 1]) {
return false;
}
}
return true;
}
};function minimumPairRemoval(nums: number[]): number {
const arr = nums.slice();
let ans = 0;
const isNonDecreasing = (a: number[]): boolean => {
for (let i = 1; i < a.length; i++) {
if (a[i] < a[i - 1]) {
return false;
}
}
return true;
};
while (!isNonDecreasing(arr)) {
let k = 0;
let s = arr[0] + arr[1];
for (let i = 1; i < arr.length - 1; ++i) {
const t = arr[i] + arr[i + 1];
if (s > t) {
s = t;
k = i;
}
}
arr[k] = s;
arr.splice(k + 1, 1);
ans++;
}
return ans;
}func minimumPairRemoval(nums []int) int {
arr := append([]int(nil), nums...)
ans := 0
isNonDecreasing := func(a []int) bool {
for i := 1; i < len(a); i++ {
if a[i] < a[i-1] {
return false
}
}
return true
}
for !isNonDecreasing(arr) {
k := 0
s := arr[0] + arr[1]
for i := 1; i < len(arr)-1; i++ {
t := arr[i] + arr[i+1]
if s > t {
s = t
k = i
}
}
arr[k] = s
copy(arr[k+1:], arr[k+2:])
arr = arr[:len(arr)-1]
ans++
}
return ans
}impl Solution {
pub fn minimum_pair_removal(nums: Vec<i32>) -> i32 {
let mut arr: Vec<i32> = nums.clone();
let mut ans: i32 = 0;
fn is_non_decreasing(a: &Vec<i32>) -> bool {
for i in 1..a.len() {
if a[i] < a[i - 1] {
return false;
}
}
true
}
while !is_non_decreasing(&arr) {
let mut k: usize = 0;
let mut s: i32 = arr[0] + arr[1];
for i in 1..arr.len() - 1 {
let t: i32 = arr[i] + arr[i + 1];
if s > t {
s = t;
k = i;
}
}
arr[k] = s;
arr.remove(k + 1);
ans += 1;
}
ans
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n^2) | O(1) | Useful for understanding the process or very small arrays |
| Heap + Doubly Linked List Simulation | O(n log n) | O(n) | General case where efficient pair selection and updates are required |
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).