Find Original Array From Doubled Array

medium array hash map greedy sorting

Problem

An array original is doubled by concatenating 2 * original to it and then shuffled. Given the shuffled array changed, return original if it was indeed doubled, otherwise return an empty array.

Inputchanged = [1, 3, 4, 2, 6, 8]

Output[1, 3, 4]

Pairs (1,2), (3,6), (4,8) — each x has its 2x partner.

changed (comma-separated)

def find_original_array(changed):
    if len(changed) % 2: return []
    from collections import Counter
    cnt = Counter(changed)
    res = []
    for x in sorted(changed, key=abs):
        if cnt[x] == 0: continue
        if cnt[2 * x] == 0: return []
        cnt[x] -= 1
        cnt[2 * x] -= 1
        res.append(x)
    return res

function findOriginalArray(changed) {
  if (changed.length % 2) return [];
  const cnt = new Map();
  for (const v of changed) cnt.set(v, (cnt.get(v) || 0) + 1);
  const res = [];
  const sorted = [...changed].sort((a, b) => Math.abs(a) - Math.abs(b));
  for (const x of sorted) {
    if ((cnt.get(x) || 0) === 0) continue;
    if ((cnt.get(2 * x) || 0) === 0) return [];
    cnt.set(x, cnt.get(x) - 1);
    cnt.set(2 * x, cnt.get(2 * x) - 1);
    res.push(x);
  }
  return res;
}

class Solution {
    public int[] findOriginalArray(int[] changed) {
        if (changed.length % 2 != 0) return new int[0];
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int v : changed) cnt.merge(v, 1, Integer::sum);
        Integer[] sorted = Arrays.stream(changed).boxed().toArray(Integer[]::new);
        Arrays.sort(sorted, (a, b) -> Integer.compare(Math.abs(a), Math.abs(b)));
        int[] res = new int[changed.length / 2];
        int k = 0;
        for (int x : sorted) {
            if (cnt.getOrDefault(x, 0) == 0) continue;
            if (cnt.getOrDefault(2 * x, 0) == 0) return new int[0];
            cnt.merge(x, -1, Integer::sum);
            cnt.merge(2 * x, -1, Integer::sum);
            res[k++] = x;
        }
        return res;
    }
}

vector<int> findOriginalArray(vector<int>& changed) {
    if (changed.size() % 2) return {};
    unordered_map<int, int> cnt;
    for (int v : changed) cnt[v]++;
    vector<int> sorted = changed;
    sort(sorted.begin(), sorted.end(), [](int a, int b){ return abs(a) < abs(b); });
    vector<int> res;
    for (int x : sorted) {
        if (cnt[x] == 0) continue;
        if (cnt[2 * x] == 0) return {};
        cnt[x]--; cnt[2 * x]--;
        res.push_back(x);
    }
    return res;
}

Explanation

Every original value x has a twin 2x hidden in the shuffled array. To rebuild the original we pair each x with its 2x, but the order we pair them in matters, so we process values from smallest absolute value first.

Why sort by absolute value? The smallest remaining number can only be an x (an original), never a 2x, because nothing smaller exists to have doubled into it. Handling it first removes ambiguity. We also bail out immediately if the length is odd, since a doubled array must be even.

We keep a counter of how many of each value are still available. Walking the sorted values, we skip any value already used up. For a live x, we must find a 2x partner; if its count is zero, the array was not a valid doubling and we return []. Otherwise we consume one x and one 2x and record x in the result.

Example: changed = [1, 3, 4, 2, 6, 8]. Sorted by magnitude it is [1, 2, 3, 4, 6, 8]. We pair 1↔2, then 3↔6, then 4↔8, giving original [1, 3, 4].

This handles negatives too, since sorting by abs still processes the magnitude-smallest first.

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