Array of Doubled Pairs
Medium · Arrays & Hashing · Array · Hash Table · Greedy · Sorting
Problem
You are given an integer array arr of even length. **Return true if you can reorder it so that arr[2 * i + 1] == 2 * arr[2 * i] for every 0 <= i < len(arr) / 2**, and false otherwise.
In other words: can the values be split into pairs (x, 2x), each value used exactly once? Values may be negative, and the partner of x is still 2x (so -3 pairs with -6).
Examples
Input: arr = [-6,4,2,-3] Output: True
Pair (-3, -6) and (2, 4).
Input: arr = [1,2,2,8] Output: False
After pairing 1 with 2, the other 2 would need a 4.
Input: arr = [0,0,5,10] Output: True
(0, 0) and (5, 10) are both valid pairs.
Constraints
- 2 <= len(arr) <= 3 · 10^4
- len(arr) is even
- -10^5 <= arr[i] <= 10^5
Approaches
- Baseline: sort, then search for each partner — time O(n²), space O(n)
Follow-up
The key is finding the value whose role is forced: the one nearest zero. The use cases change the pairing rule to x + k and the group size to three.
Related problems
Start free on Cariara · Coding problems · System design studio
