Maximize Score After Pair Deletions

Maximize Score After Pair Deletions

What is this problem about?

(Note: This logic refers to variations of paired array deletions based on conditions like "arr[i] * 2 <= arr[j]" or similar pairing logic to maximize score/deletions). You are given a sorted integer array. You are allowed to pair an element arr[i] with an element arr[j] and delete them both from the array, provided they meet a specific mathematical condition (e.g., arr[i] * 2 <= arr[j]). Your objective is to find the maximum number of pairs you can successfully delete.

Why is this asked in interviews?

This is a Two Pointers and Greedy algorithm problem. It tests your ability to pair elements without overlapping. Interviewers use it to see if candidates can recognize that trying to pair adjacent elements greedily is flawed, and that splitting the array precisely in half is the optimal strategy to maximize "distance" between paired elements.

Algorithmic pattern used

The best approach is the Two Pointers (Split Array) pattern. Because the array is sorted, pairing an element with its immediate neighbor often blocks future pairs. To maximize matches, you should pair the smallest elements in the array with the largest elements in the array.

1. Place a left pointer at index 0.
2. Place a right pointer exactly in the middle of the array n / 2.
3. Iterate: If the condition is met (e.g., arr[left] * 2 <= arr[right]), it's a valid pair! Increment both left and right, and increase your score. If the condition is NOT met, the right element is too small, so just increment right to try a larger element.

Example explanation

Assume condition arr[i] * 2 <= arr[j]. Array: [1, 2, 3, 6]. Length = 4.

• left starts at 0 (value 1).
• right starts at 2 (value 3).
• Check: $1 \times 2 \le 3$. Valid! We form pair (1, 3). Score = 1.
• Move both. left = 1 (value 2). right = 3 (value 6).
• Check: $2 \times 2 \le 6$. Valid! We form pair (2, 6). Score = 2. Maximum pairs deleted is 2.

If we had tried a sliding window from left to right, we might pair 1 and 2 (if allowed), leaving 3 and 6, which might break depending on constraints. Splitting ensures smalls pair with bigs optimally.

Common mistakes candidates make

A very common mistake is using two pointers starting from the two extreme ends (left=0, right=N-1) and moving inward. This often leads to sub-optimal pairings where the absolute largest element is wasted on the absolute smallest element, stranding the middle elements. Splitting the array at N/2 and letting both pointers move to the right concurrently guarantees maximum throughput.

Interview preparation tip

For paired deletion problems on sorted arrays, always ask yourself: "Should the pointers converge inward, or slide in parallel?" If the condition requires a significant gap between values (like $x \times 2 \le y$), sliding two pointers in parallel starting from 0 and N/2 is almost universally the optimal greedy strategy.