3507. Minimum Pair Removal to Sort Array I

UnknownView on LeetCode

Array Linked List Simulation

Time: O(n²)

Space: O(n)

Problem Overview

While the array is not non-decreasing, remove one adjacent pair with the minimum sum and replace them by their sum.

Intuition

While the array is not non-decreasing, remove one adjacent pair with the minimum sum and replace them by their sum. Count operations until no inversion remains. Each removal shortens the list by one element.

Algorithm

1Loop while array has inversion (nums[i] > nums[i+1]).
2Among all adjacent pairs, find index i with minimum nums[i]+nums[i+1] (smallest index on ties if required).
3Replace pair at i with their sum; delete nums[i+1].
4Increment operation count.
5Return count when sorted.

Example Walkthrough

Input: nums = [5,2,3,1]

1.Inversion exists. Min adjacent sum might be 2+3=5 at index 1.
2.Repeat until non-decreasing.

Output: minimum operations

Common Pitfalls

•Pick globally minimum pair sum among adjacent pairs each step.
•Check sorted with adjacent compare, not full sort each time.
•Simulation O(n²) per step is acceptable for small n in problem.

3507.cs

// Approach: Simulate removing min-sum adjacent pairs until array is non-decreasing.
// Time: O(n²) Space: O(n)

public class Solution
{
    public int MinimumPairRemoval(int[] nums)
    {
        int ans = 0;
        List<int> numsList = nums.ToList();

        while (HasInversion(numsList))
        {
            List<int> pairSums = new List<int>();
            for (int i = 0; i < numsList.Count - 1; ++i)
                pairSums.Add(numsList[i] + numsList[i + 1]);

            int minPairSum = int.MaxValue;
            int minPairIndex = -1;
            for (int i = 0; i < pairSums.Count; ++i)
            {
                if (pairSums[i] < minPairSum)
                {
                    minPairSum = pairSums[i];
                    minPairIndex = i;
                }
            }

            numsList[minPairIndex] = minPairSum;
            numsList.RemoveAt(minPairIndex + 1);
            ++ans;
        }

        return ans;
    }

    private bool HasInversion(List<int> nums)
    {
        for (int i = 0; i < nums.Count - 1; ++i)
        {
            if (nums[i] > nums[i + 1])
                return true;
        }
        
        return false;
    }
}

Was this solution helpful?