3510. Minimum Pair Removal to Sort Array II LeetCode Solution
In this guide, you will get 3510. Minimum Pair Removal to Sort Array II LeetCode Solution with the best time and space complexity. The solution to Minimum Pair Removal to Sort Array II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Minimum Pair Removal to Sort Array II solution in C++
- Minimum Pair Removal to Sort Array II solution in Java
- Minimum Pair Removal to Sort Array II solution in Python
- Additional Resources
Problem Statement of Minimum Pair Removal to Sort Array II
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
Complexity Analysis
- Time Complexity: O(n\log n)
- Space Complexity: O(n)
3510. Minimum Pair Removal to Sort Array II LeetCode Solution in C++
class Solution {
public:
int minimumPairRemoval(vector<int>& nums) {
const int n = nums.size();
int ans = 0;
int inversionsCount = 0;
vector<int> nextIndices(n);
vector<int> prevIndices(n);
vector<long> values(nums.begin(), nums.end());
// Custom comparator for the set
auto comp = [](const pair<long, int>& a, const pair<long, int>& b) {
return a.first < b.first || (a.first == b.first && a.second < b.second);
};
set<pair<long, int>, decltype(comp)> pairSums(comp);
for (int i = 0; i < n; ++i) {
nextIndices[i] = i + 1;
prevIndices[i] = i - 1;
}
for (int i = 0; i < n - 1; ++i)
pairSums.insert({(long)nums[i] + nums[i + 1], i});
for (int i = 0; i < n - 1; ++i)
if (nums[i + 1] < nums[i])
++inversionsCount;
while (inversionsCount > 0) {
++ans;
auto smallestPair = *pairSums.begin();
pairSums.erase(pairSums.begin());
const long pairSum = smallestPair.first;
const int currIndex = smallestPair.second;
const int nextIndex = nextIndices[currIndex];
const int prevIndex = prevIndices[currIndex];
if (prevIndex >= 0) {
const long oldPairSum = values[prevIndex] + values[currIndex];
const long newPairSum = values[prevIndex] + pairSum;
pairSums.erase({oldPairSum, prevIndex});
pairSums.insert({newPairSum, prevIndex});
if (values[prevIndex] > values[currIndex])
--inversionsCount;
if (values[prevIndex] > pairSum)
++inversionsCount;
}
if (values[nextIndex] < values[currIndex])
--inversionsCount;
const int nextNextIndex = (nextIndex < n) ? nextIndices[nextIndex] : n;
if (nextNextIndex < n) {
const long oldPairSum = values[nextIndex] + values[nextNextIndex];
const long newPairSum = pairSum + values[nextNextIndex];
pairSums.erase({oldPairSum, nextIndex});
pairSums.insert({newPairSum, currIndex});
if (values[nextNextIndex] < values[nextIndex])
--inversionsCount;
if (values[nextNextIndex] < pairSum)
++inversionsCount;
prevIndices[nextNextIndex] = currIndex;
}
nextIndices[currIndex] = nextNextIndex;
values[currIndex] = pairSum;
}
return ans;
}
};
/* code provided by PROGIEZ */3510. Minimum Pair Removal to Sort Array II LeetCode Solution in Java
class Solution {
public int minimumPairRemoval(int[] nums) {
final int n = nums.length;
int ans = 0;
int inversionsCount = 0;
int[] nextIndices = new int[n];
int[] prevIndices = new int[n];
long[] values = Arrays.stream(nums).mapToLong(i -> i).toArray();
TreeSet<Pair<Long, Integer>> pairSums =
new TreeSet<>(Comparator.comparingLong(Pair<Long, Integer>::getKey)
.thenComparingInt(Pair<Long, Integer>::getValue));
for (int i = 0; i < n; ++i) {
nextIndices[i] = i + 1;
prevIndices[i] = i - 1;
}
for (int i = 0; i < n - 1; ++i)
pairSums.add(new Pair<>((long) nums[i] + nums[i + 1], i));
for (int i = 0; i < n - 1; ++i)
if (nums[i + 1] < nums[i])
++inversionsCount;
while (inversionsCount > 0) {
++ans;
Pair<Long, Integer> smallestPair = pairSums.pollFirst();
final long pairSum = smallestPair.getKey();
final int currIndex = smallestPair.getValue();
final int nextIndex = nextIndices[currIndex];
final int prevIndex = prevIndices[currIndex];
if (prevIndex >= 0) {
final long oldPairSum = values[prevIndex] + values[currIndex];
final long newPairSum = values[prevIndex] + pairSum;
pairSums.remove(new Pair<>(oldPairSum, prevIndex));
pairSums.add(new Pair<>(newPairSum, prevIndex));
if (values[prevIndex] > values[currIndex])
--inversionsCount;
if (values[prevIndex] > pairSum)
++inversionsCount;
}
if (values[nextIndex] < values[currIndex])
--inversionsCount;
final int nextNextIndex = (nextIndex < n) ? nextIndices[nextIndex] : n;
if (nextNextIndex < n) {
final long oldPairSum = values[nextIndex] + values[nextNextIndex];
final long newPairSum = pairSum + values[nextNextIndex];
pairSums.remove(new Pair<>(oldPairSum, nextIndex));
pairSums.add(new Pair<>(newPairSum, currIndex));
if (values[nextNextIndex] < values[nextIndex])
--inversionsCount;
if (values[nextNextIndex] < pairSum)
++inversionsCount;
prevIndices[nextNextIndex] = currIndex;
}
nextIndices[currIndex] = nextNextIndex;
values[currIndex] = pairSum;
}
return ans;
}
}
// code provided by PROGIEZ3510. Minimum Pair Removal to Sort Array II LeetCode Solution in Python
from sortedcontainers import SortedList
class Solution:
def minimumPairRemoval(self, nums: list[int]) -> int:
n = len(nums)
ans = 0
inversionsCount = sum(nums[i + 1] < nums[i] for i in range(n - 1))
nextIndices = [i + 1 for i in range(n)]
prevIndices = [i - 1 for i in range(n)]
pairSums = SortedList((a + b, i)
for i, (a, b) in enumerate(itertools.pairwise(nums)))
while inversionsCount > 0:
ans += 1
smallestPair = pairSums.pop(0)
pairSum, currIndex = smallestPair
nextIndex = nextIndices[currIndex]
prevIndex = prevIndices[currIndex]
if prevIndex >= 0:
oldPairSum = nums[prevIndex] + nums[currIndex]
newPairSum = nums[prevIndex] + pairSum
pairSums.remove((oldPairSum, prevIndex))
pairSums.add((newPairSum, prevIndex))
if nums[prevIndex] > nums[currIndex]:
inversionsCount -= 1
if nums[prevIndex] > pairSum:
inversionsCount += 1
if nums[nextIndex] < nums[currIndex]:
inversionsCount -= 1
nextNextIndex = nextIndices[nextIndex] if nextIndex < n else n
if nextNextIndex < n:
oldPairSum = nums[nextIndex] + nums[nextNextIndex]
newPairSum = pairSum + nums[nextNextIndex]
pairSums.remove((oldPairSum, nextIndex))
pairSums.add((newPairSum, currIndex))
if nums[nextNextIndex] < nums[nextIndex]:
inversionsCount -= 1
if nums[nextNextIndex] < pairSum:
inversionsCount += 1
prevIndices[nextNextIndex] = currIndex
nextIndices[currIndex] = nextNextIndex
nums[currIndex] = pairSum
return ans
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.