3510. Minimum Pair Removal to Sort Array II
SourceWeekly Contest 444 Q4DifficultyHardRating2608
Description
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
Solutions
Solution 1: Sorted Set
Thinking
The \(O(n^2)\) simulation of the previous problem fails at \(n \le 10^5\). We still merge the adjacent pair with the smallest sum, but a full scan each time is too slow.
A sorted set keyed by \((\textit{sum}, i)\) yields the minimum pair; another stores live indices so the left and right neighbors are \(O(\log n)\). An \(\textit{inv}\) counter tracks descending adjacent pairs and is updated only at the two or three affected places, stopping when \(\textit{inv}=0\).
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 \(\textit{idx}\) to store the indices of remaining elements in the current array, and use the variable \(\textit{inv}\) to record the number of inversions in the current array. Initially, we traverse the array \(\textit{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 \(\textit{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 \(\textit{idx}\)) is the adjacent element pair with the minimum sum in the current array. If \(\textit{nums}[i] > \textit{nums}[j]\), this element pair is an inversion, and after merging and replacing, the number of inversions \(\textit{inv}\) decreases by one.
Next, we need to update the element pairs related to indices \(i\) and \(j\):
-
If index \(i\) has a predecessor index \(h\) in the sorted set \(\textit{idx}\), we need to update the element pair \((h, i)\). If \(\textit{nums}[h] > \textit{nums}[i]\), this element pair is an inversion, and after merging and replacing, the number of inversions \(\textit{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 \(\textit{nums}[h] > s\), the new element pair is an inversion, and after merging and replacing, the number of inversions \(\textit{inv}\) increases by one.
-
If index \(j\) has a successor index \(k\) in the sorted set \(\textit{idx}\), we need to update the element pair \((j, k)\). If \(\textit{nums}[j] > \textit{nums}[k]\), this element pair is an inversion, and after merging and replacing, the number of inversions \(\textit{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 > \textit{nums}[k]\), the new element pair is an inversion, and after merging and replacing, the number of inversions \(\textit{inv}\) increases by one.
Next, we replace the element at index \(i\) with \(s\) and remove index \(j\) from the sorted set \(\textit{idx}\). We repeat the above process until the number of inversions \(\textit{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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | |