Find Original Array From Doubled Array

Find Original Array From Doubled Array

What is this problem about?

The Find Original Array From Doubled Array interview question is a reconstruction challenge. You are given a "changed" array that was supposedly formed by taking an original array and appending twice the value of every element to it. For example, if the original was [1, 3, 4], the changed array could be [1, 3, 4, 2, 6, 8]. Your task is to find the original array or return an empty array if the input is not a valid doubled array.

Why is this asked in interviews?

Companies like Google and Microsoft ask the Find Original Array coding problem to test your proficiency with Hash Tables and Sorting. It evaluations if you can identify a clear starting point (the smallest element) and greedily match it with its double. It’s a test of logical consistency and frequency management.

Algorithmic pattern used

This problem follows the Greedy and Frequency Counting patterns.

1. Initial Check: If the array length is odd, it can't be a doubled array. Return [].
2. Frequency Map: Count occurrences of every number in a hash map.
3. Sort: Sort the unique keys of the array.
4. Matching: Iterate through the sorted numbers. For each number $x$:
   • If count[x] is $> 0$:
     • We need count[x] occurrences of $2x$ to pair them up.
     • If count[2x] < count[x], reconstruction is impossible. Return [].
     • Add $x$ to the result count[x] times and subtract that from count[2x].

Example explanation

Array: [1, 3, 4, 2, 6, 8]

1. Sorted: [1, 2, 3, 4, 6, 8]. Frequencies: {1:1, 2:1, 3:1, 4:1, 6:1, 8:1}.
2. Smallest is 1. Need double (2). 2 exists. Add 1 to original. count[2] becomes 0.
3. Next available is 3. Need double (6). 6 exists. Add 3 to original. count[6] becomes 0.
4. Next available is 4. Need double (8). 8 exists. Add 4 to original. count[8] becomes 0. Result: [1, 3, 4].

Common mistakes candidates make

• Not Sorting: Trying to match pairs in a random order, which leads to ambiguity (e.g., does 2 pair with 1 or 4?).
• Zero Handling: Forgetting that 0 is its own double ($0 imes 2 = 0$), so the count of zeros must be even.
• Incomplete Matching: Failing to verify that every single element in the changed array was successfully paired.

Interview preparation tip

Whenever you need to "pair" elements based on a numeric relationship, Sorting is usually your first step. It provides a deterministic order that allows for a greedy matching strategy. This is a vital Hash Table interview pattern.