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 <= 50-1000 <= nums[i] <= 1000Problem 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.
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.
| 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 |
Minimum Pair Removal to Sort Array I | Simple Explanation | Leetcode 3507 | codestorywithMIK • codestorywithMIK • 9,761 views views
Watch 9 more video solutions →Practice Minimum Pair Removal to Sort Array I with our built-in code editor and test cases.
Practice on FleetCode