Minimum Array Length After Pair Removals - Video Solutions

Problem Overview: You are given a non‑decreasing array. In one operation, pick two indices i < j where nums[i] < nums[j] and remove both elements. The goal is to perform operations so the remaining array length is as small as possible.

Approach 1: Two-Pointer Greedy Pairing (O(n) time, O(1) space)

The array is already sorted, which makes pairing straightforward. Split the array conceptually into two halves. Use two pointers: i starting at the beginning (smaller values) and j starting around the middle (potential larger partners). If nums[i] < nums[j], you can form a valid pair, so increment both pointers and count the pair. If not, move j forward to find a larger element. This greedy pairing works because matching the smallest available element with the earliest valid larger element preserves larger values for future matches. After scanning once, the remaining length is n - 2 * pairs. The algorithm runs in linear time and constant space, making it ideal for large inputs and a common pattern in two pointers problems on sorted arrays.

Approach 2: Greedy Matching Using Frequency Count (O(n) time, O(n) space)

This approach focuses on value frequencies rather than indices. Count how often each number appears using a frequency map or counter from hash table utilities. The limiting factor is the most frequent element. If one value appears more than half the array (maxFreq > n/2), those extra elements cannot all be paired with distinct larger values. The leftover length becomes 2 * maxFreq - n. Otherwise, elements can mostly cancel each other out and the remaining length is simply n % 2. This reasoning comes from the observation that every valid operation removes two different values, so the most frequent value determines how many unmatched elements remain. The approach uses counting and greedy reasoning often seen in greedy and frequency‑based array problems.

Recommended for interviews: The two‑pointer greedy approach is usually the expected solution because it directly uses the sorted property and runs in O(n) time with O(1) extra space. The frequency insight is also valuable because it reveals the mathematical structure of the problem. Demonstrating both shows strong understanding: the pointer solution proves implementation skill, while the counting observation shows deeper algorithmic reasoning.