{x}
blog image

Find Original Array From Doubled Array

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 <= 105
  • 0 <= changed[i] <= 105

Solution Explanation: Finding the Original Array from a Doubled Array

This problem asks us to reconstruct an original array original given a shuffled doubled array changed. The changed array is created by taking each element in original, doubling it, and then shuffling the combined elements. The challenge is to determine if a valid original array exists and, if so, to reconstruct it.

Approach: Sorting and Frequency Counting

The key insight is that if changed is a doubled array, then for every element x in original, its double 2x must also exist in changed. Moreover, the count of x in original must equal the count of 2x in changed. This leads us to a solution using sorting and frequency counting:

  1. Sort changed: Sorting allows us to efficiently check for pairs (x, 2x).

  2. Count Frequencies: We use a hash map (or array if the numbers are within a known range) to count the occurrences of each number in changed.

  3. Iterate and Reconstruct: We iterate through the sorted changed array. For each element x:

    • If its count is zero, we skip it.
    • We decrement its count.
    • We check if 2x exists and has a count greater than zero. If not, we know changed is not a doubled array, and we return an empty array.
    • If 2x exists, we decrement its count and add x to the original array.

  4. Return original: After iterating through all elements, we return the reconstructed original array.

Time and Space Complexity Analysis

  • Time Complexity: The dominant operation is sorting the changed array, which takes O(n log n) time, where n is the length of changed. The subsequent iteration and frequency counting are O(n). Therefore, the overall time complexity is O(n log n).

  • Space Complexity: We use a hash map (or array) to store the frequencies, which takes O(n) space in the worst case (all numbers are unique). The original array also takes O(n/2) space which simplifies to O(n). Therefore, the overall space complexity is O(n).

Code Implementation in Multiple Languages

The following code implements the solution in several programming languages. The core logic remains consistent across all implementations.

Python3

from collections import Counter
 
class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        if len(changed) % 2 != 0:
            return []  # Odd length cannot be a doubled array
 
        changed.sort()
        count = Counter(changed)
        original = []
        for num in changed:
            if count[num] == 0:
                continue
            count[num] -= 1
            if count[num * 2] == 0:
                return [] # No double found
            count[num * 2] -= 1
            original.append(num)
        return original

Java

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
 
class Solution {
    public int[] findOriginalArray(int[] changed) {
        if (changed.length % 2 != 0) return new int[0];
 
        Arrays.sort(changed);
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : changed) count.put(num, count.getOrDefault(num, 0) + 1);
 
        int[] original = new int[changed.length / 2];
        int index = 0;
        for (int num : changed) {
            if (count.get(num) == 0) continue;
            count.put(num, count.get(num) - 1);
            if (!count.containsKey(num * 2) || count.get(num * 2) == 0) return new int[0];
            count.put(num * 2, count.get(num * 2) - 1);
            original[index++] = num;
        }
        return original;
    }
}

C++

#include <vector>
#include <map>
#include <algorithm>
 
using namespace std;
 
class Solution {
public:
    vector<int> findOriginalArray(vector<int>& changed) {
        if (changed.size() % 2 != 0) return {};
 
        sort(changed.begin(), changed.end());
        map<int, int> count;
        for (int num : changed) count[num]++;
 
        vector<int> original;
        for (int num : changed) {
            if (count[num] == 0) continue;
            count[num]--;
            if (count.find(num * 2) == count.end() || count[num * 2] == 0) return {};
            count[num * 2]--;
            original.push_back(num);
        }
        return original;
    }
};

Javascript

/**
 * @param {number[]} changed
 * @return {number[]}
 */
var findOriginalArray = function(changed) {
    if (changed.length % 2 !== 0) return [];
    changed.sort((a, b) => a - b);
    const count = {};
    for (let num of changed) count[num] = (count[num] || 0) + 1;
    const original = [];
    for (let num of changed) {
        if (count[num] === 0) continue;
        count[num]--;
        if (!count[num * 2] || count[num * 2] === 0) return [];
        count[num * 2]--;
        original.push(num);
    }
    return original;
};

This detailed explanation, along with the multiple language implementations, provides a comprehensive understanding of how to solve the "Find Original Array From Doubled Array" problem efficiently. Remember to handle edge cases, such as arrays with odd lengths, to ensure the robustness of your solution.