Don't be ashamed of N^2 III

Remember that for smaller Ns, an N^2 solution works just fine. This is an example of it. N in this case is 50, hence an N^2 solution is trivial, almost linear. One function to check if we're done, and then the main function to perform the operations, resulting in N^2. Code is down below, cheers, ACC.

Minimum Pair Removal to Sort Array I - LeetCode

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 <= 50
• -1000 <= nums[i] <= 1000

public int MinimumPairRemoval(int[] nums)
{
    List numbers = nums.ToList();

    int numberOperations = 0;
    while (!IsNonDecreasingList(numbers))
    {
        int minSum = Int32.MaxValue;
        int index = -1;

        for (int i = 0; i < numbers.Count - 1; i++)
        {
            if (numbers[i] + numbers[i + 1] < minSum)
            {
                minSum = numbers[i] + numbers[i + 1];
                index = i;
            }
        }

        numbers[index] = minSum;
        numbers.RemoveAt(index + 1);
        numberOperations++;
    }

    return numberOperations;
}

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

    return true;
}