Minimum Array Length After Pair Removals

The core idea is that to maximize the number of removals, we should pair smaller elements with larger elements. Since the input array nums is sorted, this naturally suggests pairing elements from the first half of the array with elements from the second half. This greedy strategy can be implemented efficiently using a two-pointer technique.

• Initialize two pointers, i starting at 0 and j starting at (n + 1) / 2, where n is the length of the array.
• Initialize a counter pairs to 0.
• Loop while i is in the first half (i.e., i < (n + 1) / 2) and j is in the second half (i.e., j < n):
  • If nums[i] < nums[j], it means we can form a pair. Increment pairs, and advance both pointers i and j.
  • Otherwise (nums[i] >= nums[j]), we cannot pair nums[i] with nums[j]. We need to find a larger element in the second half for nums[i], so we only advance j.
• After the loop terminates, the total number of elements removed is 2 * pairs.
• The minimum length of the remaining array is n - 2 * pairs.

We use two pointers, i and j, to traverse the first and second halves of the array, respectively. The pointer i starts at the beginning of the array (0), and j starts at the beginning of the second half (at index (n + 1) / 2 to handle both even and odd length arrays correctly). We iterate through the array and try to form pairs. If nums[i] is smaller than nums[j], we have a valid pair. We count this pair and advance both pointers to look for the next pair. If nums[i] is not smaller than nums[j], we can't pair them. Since nums[i] is fixed, we need to find a larger element in the second half, so we advance j while keeping i the same. The process continues until one of the pointers goes out of its respective half's bounds. The final answer is the initial length minus twice the number of pairs found.

class Solution {
    public int minLengthAfterRemovals(List<Integer> nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }

        int i = 0;
        int j = (n + 1) / 2;
        int pairs = 0;

        while (i < n / 2 && j < n) {
            if (nums.get(i) < nums.get(j)) {
                pairs++;
                i++;
                j++;
            } else {
                j++;
            }
        }

        return n - 2 * pairs;
    }
}