Array of Doubled Pairs - Solution & Explanation

Problem Overview: You receive an integer array arr. The task is to check whether the array can be reordered so that for every element x, there exists another element 2x. Each number must be used exactly once in a pair. Negative numbers and zeros make the pairing logic trickier, which is why ordering and careful counting are required.

Approach 1: Sorting and Counting (Time: O(n log n), Space: O(n))

This approach combines sorting with frequency counting using a hash table. First count the frequency of each number in a map. Then sort the array by absolute value so smaller magnitudes are processed before their doubles. This order is critical because pairing a number early ensures its double still exists later.

Iterate through the sorted array. For each value x, check if its count is already zero (already paired). If not, verify that 2 * x exists in the frequency map with a positive count. Decrease the counts for both x and 2x. If the double is missing, the array cannot form valid doubled pairs.

The key insight is processing numbers by absolute value. Without this ordering, negative numbers could incorrectly consume values needed for other pairs. Sorting guarantees that when you try to match x, its double has not been prematurely used. This strategy is considered a classic greedy pairing technique.

Approach 2: Two-pointer Technique (Time: O(n log n), Space: O(1) to O(n))

This method starts by sorting the array. After sorting, the algorithm attempts to match smaller numbers with their doubles using two scanning indices. One pointer tracks candidate base numbers while the second searches ahead for elements equal to double the current value.

As the pointers move, matched elements are marked or skipped so they are not reused. If the second pointer finds 2 * arr[i], the pair is recorded and both pointers move forward. If the search pointer advances past possible matches without finding the double, the pairing fails.

This approach emphasizes sequential scanning rather than explicit frequency maps. It works best when the array is already sorted or when memory usage should stay minimal. However, the implementation becomes more delicate when duplicates or negative numbers appear, which is why many engineers prefer the counting approach for clarity.

Recommended for interviews: The sorting + hash counting solution is what most interviewers expect. It demonstrates control over hash map frequency tracking and careful ordering logic. Showing a brute pairing idea first can communicate intuition, but implementing the greedy counting approach shows strong problem-solving skills and handles edge cases like negatives and zeros correctly.