Array of Doubled Pairs — Solution in Python, Java & C++
Array of Doubled Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Array of Doubled Pairs is a medium coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Sorting, Greedy
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
arr has an even length. Decide whether its elements can be rearranged so that, for every i with 0 <= i < arr.length / 2, the element at position 2 * i + 1 is exactly twice the element at position 2 * i.
In other words: can the whole array be split into pairs (x, 2x), each element used exactly once? Return true if it can.
Example 1
Input: arr = [-6,4,2,-3]
Output: true
Explanation: Pairs `(2, 4)` and `(-3, -6)`.
Example 2
Input: arr = [5,1,5,10]
Output: false
Explanation: `1` needs a `2` and there is none.
Example 3
Input: arr = [0,4,0,2]
Output: true
Explanation: `(0, 0)` and `(2, 4)`.
Constraints
2 <= arr.length <= 3 * 10^4arr.length is even-10^5 <= arr[i] <= 10^5
Hints for Array of Doubled Pairs
Hint 1
Think about the element with the smallest absolute value: can it be the double in its pair?
Hint 2
No — its partner would have to be half of it, which is smaller in absolute value. So it must pair with twice itself.
Hint 3
Count the values, visit them in increasing absolute value, and match each remaining copy of
xwith a copy of2x. Zeros pair among themselves.
How to solve Array of Doubled Pairs
The element of least absolute value has no smaller half available, so it is forced to pair with its double; repeating that forced choice decides the answer greedily.
Approach
- Count every value.
- Visit the distinct values in increasing order of absolute value.
- For
x = 0, the count must be even (zeros pair with each other). - For any other
xwithccopies left, require at leastccopies of2x, then removeccopies of2x. - If every value is settled, return
true.
Why it works
When x is processed, every value of smaller absolute value has already been settled, so the only remaining partner for a copy of x is 2x (its half x / 2 would be smaller in absolute value and is already used up). The choice is forced, so failing here means no arrangement exists, and succeeding at every step builds one.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Sorting by plain value breaks negatives: for
-4the partner is-8, which is smaller. Sort by absolute value instead. - Zero is its own double, so its copies must pair among themselves — an odd count fails.
- Decrement the double's count by all copies of
xat once; otherwise the loop may revisit2xwith a stale count.
Reference solution
Python
from typing import List
from collections import Counter
def canReorderDoubled(arr: List[int]) -> bool:
count = Counter(arr)
for x in sorted(count, key=abs):
c = count[x]
if c == 0:
continue
if x == 0:
if c % 2:
return False
continue
if count[2 * x] < c:
return False
count[2 * x] -= c
return TrueJava
public static boolean canReorderDoubled(int[] arr) {
Map<Integer, Integer> count = new HashMap<>();
for (int v : arr) count.merge(v, 1, Integer::sum);
List<Integer> keys = new ArrayList<>(count.keySet());
keys.sort((a, b) -> Integer.compare(Math.abs(a), Math.abs(b)));
for (int x : keys) {
int c = count.get(x);
if (c == 0) continue;
if (x == 0) {
if (c % 2 != 0) return false;
continue;
}
int d = count.getOrDefault(2 * x, 0);
if (d < c) return false;
count.put(2 * x, d - c);
}
return true;
}C++
bool canReorderDoubled(vector<int>& arr) {
unordered_map<int, int> count;
for (int v : arr) count[v]++;
vector<int> keys;
for (auto& p : count) keys.push_back(p.first);
sort(keys.begin(), keys.end(), [](int a, int b) { return abs(a) < abs(b); });
for (int x : keys) {
int c = count[x];
if (c == 0) continue;
if (x == 0) {
if (c % 2 != 0) return false;
continue;
}
auto it = count.find(2 * x);
if (it == count.end() || it->second < c) return false;
it->second -= c;
}
return true;
}JavaScript
var canReorderDoubled = function(arr) {
var count = new Map();
for (var i = 0; i < arr.length; i++) count.set(arr[i], (count.get(arr[i]) || 0) + 1);
var keys = Array.from(count.keys()).sort(function(a, b) { return Math.abs(a) - Math.abs(b); });
for (var k = 0; k < keys.length; k++) {
var x = keys[k];
var c = count.get(x);
if (c === 0) continue;
if (x === 0) {
if (c % 2 !== 0) return false;
continue;
}
var d = count.get(2 * x) || 0;
if (d < c) return false;
count.set(2 * x, d - c);
}
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets