Array of Doubled Pairs

medium greedy sorting hash map

Problem

Given an integer array arr of even length, return true if and only if it is possible to reorder it such that arr[2 * i + 1] == 2 * arr[2 * i] for every 0 ≤ i < len(arr) / 2.

Inputarr = [4, -2, 2, -4]

Outputtrue

We can group as [-2, -4] and [2, 4], so each pair (x, 2x) is formed.

arr (comma-separated, even length)

def can_reorder_doubled(arr):
    count = {}
    for x in arr:
        count[x] = count.get(x, 0) + 1
    for x in sorted(count, key=abs):
        if count[x] == 0:
            continue
        if count.get(2 * x, 0) < count[x]:
            return False
        count[2 * x] -= count[x]
        count[x] = 0
    return True

function canReorderDoubled(arr) {
  const count = new Map();
  for (const x of arr) count.set(x, (count.get(x) || 0) + 1);
  const keys = [...count.keys()].sort((a, b) => Math.abs(a) - Math.abs(b));
  for (const x of keys) {
    if (count.get(x) === 0) continue;
    const dbl = count.get(2 * x) || 0;
    if (dbl < count.get(x)) return false;
    count.set(2 * x, dbl - count.get(x));
    count.set(x, 0);
  }
  return true;
}

class Solution {
    public boolean canReorderDoubled(int[] arr) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int x : arr) count.merge(x, 1, Integer::sum);
        Integer[] keys = count.keySet().toArray(new Integer[0]);
        Arrays.sort(keys, (a, b) -> Math.abs(a) - Math.abs(b));
        for (int x : keys) {
            if (count.get(x) == 0) continue;
            int dbl = count.getOrDefault(2 * x, 0);
            if (dbl < count.get(x)) return false;
            count.put(2 * x, dbl - count.get(x));
            count.put(x, 0);
        }
        return true;
    }
}

bool canReorderDoubled(vector<int>& arr) {
    map<int, int> count;
    for (int x : arr) count[x]++;
    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) {
        if (count[x] == 0) continue;
        if (count[2 * x] < count[x]) return false;
        count[2 * x] -= count[x];
        count[x] = 0;
    }
    return true;
}

Explanation

We must pair every number with its double. The hard part is deciding which number is the "base" of a pair and which is the "double", because a number like 4 could be the double of 2 or the base for 8. The fix is to always commit the smallest-magnitude numbers first.

We count how many times each value appears in a map count. Then we go through the distinct values sorted by absolute value (key=abs). The number closest to zero in each chain can never be someone else's double, so it must act as a base and needs its own double available.

For the current value x with count[x] copies left, we require at least that many copies of 2*x. If there are not enough (count[2*x] < count[x]), pairing is impossible and we return False. Otherwise we consume that many doubles and zero out x.

Sorting by absolute value handles negatives correctly: for negatives the "double" is more negative (larger magnitude), so -2 is processed before -4, just like 2 before 4.

Example: arr=[4,-2,2,-4]. By magnitude we see 2 first and pair it with 4, then -2 pairs with -4. Everything matches, so the answer is true.

Time: O(n log n) Space: O(n)