3510. Minimum Pair Removal to Sort Array II
Approach
Doubly linked list + priority queue; always remove the minimum-sum adjacent pair.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Linked list problems often use the fast/slow pointer (Floyd's algorithm) for cycle detection and finding the middle, and dummy head nodes for clean insertion/deletion. Reverse operations should be done iteratively to avoid stack overflow on large lists.
Simulation problems require implementing the described process step by step. Focus on correctly handling edge cases and state transitions. Common in geometry, game problems, and string manipulation. Optimize only if the naive simulation exceeds the time limit.
// Approach: Doubly linked list + priority queue; always remove the minimum-sum adjacent pair.
// Time: O(n log n) Space: O(n)
public class Solution
{
public int MinimumPairRemoval(int[] nums)
{
int n = nums.Length;
int ans = 0;
int inversionsCount = 0;
int[] nextIndices = new int[n];
int[] prevIndices = new int[n];
long[] values = nums.Select(x => (long)x).ToArray();
var pairSums = new SortedSet<(long sum, int index)>(
Comparer<(long sum, int index)>.Create((a, b) =>
{
int cmp = a.sum.CompareTo(b.sum);
if (cmp == 0) return a.index.CompareTo(b.index);
return cmp;
}));
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(((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;
var smallestPair = pairSums.Min;
pairSums.Remove(smallestPair);
long pairSum = smallestPair.sum;
int currIndex = smallestPair.index;
int nextIndex = nextIndices[currIndex];
int prevIndex = prevIndices[currIndex];
if (prevIndex >= 0)
{
long oldPairSum = values[prevIndex] + values[currIndex];
long newPairSum = values[prevIndex] + pairSum;
pairSums.Remove((oldPairSum, prevIndex));
pairSums.Add((newPairSum, prevIndex));
if (values[prevIndex] > values[currIndex])
--inversionsCount;
if (values[prevIndex] > pairSum)
++inversionsCount;
}
if (nextIndex < n && values[nextIndex] < values[currIndex])
--inversionsCount;
int nextNextIndex = (nextIndex < n) ? nextIndices[nextIndex] : n;
if (nextNextIndex < n)
{
long oldPairSum = values[nextIndex] + values[nextNextIndex];
long newPairSum = pairSum + values[nextNextIndex];
pairSums.Remove((oldPairSum, nextIndex));
pairSums.Add((newPairSum, currIndex));
if (values[nextNextIndex] < values[nextIndex])
--inversionsCount;
if (values[nextNextIndex] < pairSum)
++inversionsCount;
prevIndices[nextNextIndex] = currIndex;
}
nextIndices[currIndex] = nextNextIndex;
values[currIndex] = pairSum;
}
return ans;
}
}