Find Original Array From Doubled Array

Medium
502.

Find Original Array From Doubled Array

Find Original Array From Doubled Array is a medium coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.

An array changed is a doubled array if it was built from some array original by appending twice the value of every element and then shuffling the result.

Given changed, return original sorted in ascending order. If changed is not a doubled array, return an empty array.

Example 1

Input
changed = [1,3,4,2,6,8]
Output
[1,3,4]
Explanation
The doubles 2, 6 and 8 pair off with 1, 3 and 4.

Example 2

Input
changed = [6,3,0,1]
Output
[]
Explanation
No valid original array produces this multiset.

Example 3

Input
changed = [1]
Output
[]
Explanation
An odd length can never be a doubled array.

Constraints

  • 1 <= changed.length <= 100000
  • 0 <= changed[i] <= 100000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} changed
 * @return {number[]}
 */
var findOriginalArray = function(changed) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Original Array From Doubled Array — Problem & Solution

Find Original Array From Doubled Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Find Original Array From Doubled Array 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

An array changed is a doubled array if it was built from some array original by appending twice the value of every element and then shuffling the result.

Given changed, return original sorted in ascending order. If changed is not a doubled array, return an empty array.

Example 1

Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]
Explanation: The doubles 2, 6 and 8 pair off with 1, 3 and 4.

Example 2

Input: changed = [6,3,0,1]
Output: []
Explanation: No valid original array produces this multiset.

Example 3

Input: changed = [1]
Output: []
Explanation: An odd length can never be a doubled array.

Constraints

  • 1 <= changed.length <= 100000
  • 0 <= changed[i] <= 100000

Hints for Find Original Array From Doubled Array

  1. Hint 1

    An odd length is an immediate rejection.

  2. Hint 2

    Process values in increasing order: the smallest remaining value can only ever be an original, never a double.

  3. Hint 3

    Zero is the awkward case — it is its own double, so it consumes two zeros per original.

How to solve Find Original Array From Doubled Array

Sort ascending and match greedily. The smallest unmatched value cannot be anyone's double (that would require a smaller positive value still in play), so it must belong to original and be paired with its double.

Approach

  1. Reject an odd-length input outright.
  2. Sort a copy and build a frequency map.
  3. Walk the sorted values. Skip any already consumed (frequency 0).
  4. Otherwise decrement the value and its double; if the double is unavailable, the input is invalid. Record the value in the answer.
  5. Return the collected values — they come out ascending because the walk is ascending.

Why it works

In a valid doubled array, the minimum element must be an original: its half would be a smaller element, contradicting minimality (for positive values). Consuming it and its double leaves a strictly smaller valid instance, so induction carries the greedy through.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • 0 doubles to itself, so a run of zeros must be even and each original consumes two of them.
  • Iterating over the map's keys in hash order instead of sorted order breaks the greedy argument.
  • Decrementing the double before checking it exists can produce negative counts that silently pass later tests.

Reference solution

Python

from typing import List

def findOriginalArray(changed: List[int]) -> List[int]:
    if len(changed) % 2 != 0:
        return []
    s = sorted(changed)
    count = {}
    for x in s:
        count[x] = count.get(x, 0) + 1
    out = []
    for x in s:
        if count.get(x, 0) == 0:
            continue
        if x == 0:
            if count[x] < 2:
                return []
            count[x] -= 2
            out.append(0)
            continue
        if count.get(x * 2, 0) == 0:
            return []
        count[x] -= 1
        count[x * 2] -= 1
        out.append(x)
    return out

Java

public static int[] findOriginalArray(int[] changed) {
    if (changed.length % 2 != 0) return new int[0];
    int[] s = changed.clone();
    Arrays.sort(s);
    HashMap<Integer, Integer> count = new HashMap<>();
    for (int x : s) count.put(x, count.getOrDefault(x, 0) + 1);
    int[] tmp = new int[s.length / 2];
    int m = 0;
    for (int x : s) {
        if (count.getOrDefault(x, 0) == 0) continue;
        if (x == 0) {
            if (count.get(0) < 2) return new int[0];
            count.put(0, count.get(0) - 2);
            tmp[m++] = 0;
            continue;
        }
        if (count.getOrDefault(x * 2, 0) == 0) return new int[0];
        count.put(x, count.get(x) - 1);
        count.put(x * 2, count.get(x * 2) - 1);
        tmp[m++] = x;
    }
    int[] out = new int[m];
    for (int i = 0; i < m; i++) out[i] = tmp[i];
    return out;
}

C++

vector<int> findOriginalArray(vector<int>& changed) {
    if (changed.size() % 2 != 0) return {};
    vector<int> s = changed;
    sort(s.begin(), s.end());
    unordered_map<int, int> count;
    for (int x : s) count[x]++;
    vector<int> out;
    for (int x : s) {
        if (count[x] == 0) continue;
        if (x == 0) {
            if (count[0] < 2) return {};
            count[0] -= 2;
            out.push_back(0);
            continue;
        }
        if (count[x * 2] == 0) return {};
        count[x]--;
        count[x * 2]--;
        out.push_back(x);
    }
    return out;
}

JavaScript

var findOriginalArray = function(changed) {
    if (changed.length % 2 !== 0) return [];
    const s = changed.slice().sort(function(a, b) { return a - b; });
    const count = {};
    for (let i = 0; i < s.length; i++) {
        const k = String(s[i]);
        count[k] = (count[k] || 0) + 1;
    }
    const out = [];
    for (let i = 0; i < s.length; i++) {
        const x = s[i];
        const kx = String(x);
        if ((count[kx] || 0) === 0) continue;
        if (x === 0) {
            if (count[kx] < 2) return [];
            count[kx] -= 2;
            out.push(0);
            continue;
        }
        const k2 = String(x * 2);
        if ((count[k2] || 0) === 0) return [];
        count[kx]--;
        count[k2]--;
        out.push(x);
    }
    return out;
};

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