Find Original Array From Doubled Array

LeetCode 2117 | Difficulty: Medium

Medium

Problem Description

An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.

Given an array changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order.

Example 1:

Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]
Explanation: One possible original array could be [1,3,4]:
- Twice the value of 1 is 1 * 2 = 2.
- Twice the value of 3 is 3 * 2 = 6.
- Twice the value of 4 is 4 * 2 = 8.
Other original arrays could be [4,3,1] or [3,1,4].

Example 2:

Input: changed = [6,3,0,1]
Output: []
Explanation: changed is not a doubled array.

Example 3:

Input: changed = [1]
Output: []
Explanation: changed is not a doubled array.

Constraints:

- `1 <= changed.length <= 10^5`

- `0 <= changed[i] <= 10^5`

Topics: Array, Hash Table, Greedy, Sorting

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Greedy

At each step, make the locally optimal choice. The challenge is proving the greedy choice leads to a global optimum. Look for: can I sort by some criterion? Does choosing the best option now ever hurt future choices?

When to use

Interval scheduling, activity selection, minimum coins (certain denominations), Huffman coding.

---

Solutions

Solution 1: C# (Best: 436 ms)

Metric	Value
Runtime	436 ms
Memory	55 MB
Date	2022-01-31

Solution

public class Solution {
    public int[] FindOriginalArray(int[] changed) {
       int n = changed.Length;
    if(n%2 != 0) return new int[0];
    Dictionary<int, int> counts = new Dictionary<int, int>();
    int[] result = new int[n/2];
    int index= 0;
    foreach(var num in changed)
    {
        if(counts.ContainsKey(num)) counts[num]++;
        else counts.Add(num, 1);
    }
    
    Array.Sort(changed);
    foreach (var num in changed)
    {
        if(counts[num]==0) continue;
        int target = num<0 ? num/2 : num*2;
        if(num<0 && num%2 != 0) return new int[0];
        if(!counts.ContainsKey(target) || index >= n/2) return new int[0];
        result[index++] = num;
        
        counts[num]--;
        counts[target]--;
    }
    return result;  
    }
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: If changed is a doubled array, you should be able to delete elements and their doubled values until the array is empty.

Hint 2: Which element is guaranteed to not be a doubled value? It is the smallest element.

Hint 3: After removing the smallest element and its double from changed, is there another number that is guaranteed to not be a doubled value?