Find Original Array From Doubled Array

Med

#1828Time: O(N^2), where N is the length of the `changed` array. The sorting takes O(N log N), but the nested loops for finding pairs dominate, resulting in a quadratic time complexity.Space: O(N), where N is the length of the `changed` array. This is for the `used` array and the `original` list which can grow up to size N/2.2 companies

Patterns

Algorithms

Data structures

Companies

Prompt

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⁵
0 <= changed[i] <= 10⁵

Approaches

3 approaches with complexity analysis and trade-offs.

This approach is a straightforward, brute-force method. The main idea is to sort the input array first. Sorting helps because for any positive number x, it ensures that x will always appear before its double 2*x in the array. After sorting, we iterate through the array. For each number, we treat it as an element of the original array and then linearly scan the rest of the array to find its corresponding double. We use a boolean array to keep track of which elements have been used to avoid pairing them more than once.

Algorithm

Check if the length of the changed array is odd. If it is, it cannot be a doubled array, so return an empty array.
Sort the changed array in non-decreasing order.
Create a boolean array used of the same size as changed, initialized to false, to keep track of numbers that have been paired.
Initialize an empty list original to store the result.
Iterate through the sorted changed array from left to right.
For each element num at index i:
- If used[i] is true, it means this number has already been used as a double for a smaller number, so skip it.
- Mark used[i] as true and add num to the original list.
- Perform a linear search for num * 2 in the rest of the array (from index i + 1).
- If an unused num * 2 is found at index j, mark used[j] as true and stop the search for this num.
- If an unused num * 2 is not found, it means changed is not a valid doubled array. Return an empty array.
If the loop completes successfully, the original list contains the result. Convert it to an array and return it.

Walkthrough

The algorithm begins by handling the base case: an array with an odd number of elements cannot be a doubled array, so we return an empty array immediately. Then, we sort the changed array. This is a key step that simplifies pairing. We iterate through the sorted array with an index i. If the element changed[i] has not been used, we add it to our potential original array. We then start a nested loop with index j from i+1 to find changed[i] * 2. To prevent using the same element twice, we maintain a used boolean array. If we find an unused match changed[j] == changed[i] * 2, we mark both elements as used and move to the next element in the outer loop. If we iterate through the entire array for a given changed[i] and cannot find its double, we conclude that the array is not a valid doubled array and return an empty array.

1import java.util.ArrayList;2import java.util.Arrays;3import java.util.List;4 5class Solution {6    public int[] findOriginalArray(int[] changed) {7        int n = changed.length;8        if (n % 2 != 0) {9            return new int[0];10        }11        Arrays.sort(changed);12        List<Integer> originalList = new ArrayList<>();13        boolean[] used = new boolean[n];14        int count = 0;15 16        for (int i = 0; i < n; i++) {17            if (used[i]) {18                continue;19            }20            int num = changed[i];21            int target = num * 2;22            boolean found = false;23            for (int j = i + 1; j < n; j++) {24                if (!used[j] && changed[j] == target) {25                    used[j] = true;26                    found = true;27                    break;28                }29            }30            if (found) {31                originalList.add(num);32                count++;33            } else {34                return new int[0];35            }36        }37 38        if (count != n / 2) {39            return new int[0];40        }41 42        return originalList.stream().mapToInt(i -> i).toArray();43    }44}

Complexity

Time

O(N^2), where N is the length of the `changed` array. The sorting takes O(N log N), but the nested loops for finding pairs dominate, resulting in a quadratic time complexity.

Space

O(N), where N is the length of the `changed` array. This is for the `used` array and the `original` list which can grow up to size N/2.

Trade-offs

Pros

Relatively simple to conceptualize and implement.

Cons

The time complexity of O(N^2) is highly inefficient and will likely result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.

This approach significantly improves the time complexity by replacing the linear search for a double with a constant-time hash map lookup. We first count the frequencies of all numbers. Then, we sort the array to ensure we always process a number x before its potential double 2x. As we iterate through the sorted array, we use the frequency map to find and consume pairs (x, 2x). If we can successfully pair up all the numbers, we have found the original array.

Algorithm

Check if the length of changed is odd. If so, return an empty array.
Create a hash map to store the frequency of each number in the changed array.
Sort the changed array. This is crucial to ensure that for any x > 0, we process x before 2*x.
Initialize an empty list or an array original of size N/2 to store the result.
Iterate through each num in the sorted changed array:
- If the frequency of num in the map is 0, it means it has already been used as a double, so we skip it.
- Decrement the frequency of num in the map.
- Calculate the double: target = num * 2.
- Check if the target exists in the map and has a frequency greater than 0.
- If yes, decrement the frequency of target and add num to the original array.
- If no, a pair cannot be formed. Return an empty array.
If the loop completes, it means all numbers were successfully paired. Return the original array.

Walkthrough

The first step is to check for the odd length edge case. We then build a frequency map of all numbers in changed. A HashMap is suitable for this. After counting, we sort the changed array. The sort is essential to avoid greedy mistakes, for instance, in an array like [2, 4, 8], we must pair (2, 4) first, not (4, 8). By processing the sorted array [2, 4, 8], we first encounter 2. We look for its double, 4, in the frequency map. We find it, use both, and add 2 to our result. Then we move to 4, but its count in the map is now zero (as it was used as a double), so we skip it. Finally, we process 8, but cannot find its double 16, so we correctly identify that this is not a valid doubled array. This process of decrementing counts in the map effectively 'removes' numbers as they are paired.

1import java.util.ArrayList;2import java.util.Arrays;3import java.util.HashMap;4import java.util.Map;5 6class Solution {7    public int[] findOriginalArray(int[] changed) {8        int n = changed.length;9        if (n % 2 != 0) {10            return new int[0];11        }12 13        Map<Integer, Integer> freq = new HashMap<>();14        for (int num : changed) {15            freq.put(num, freq.getOrDefault(num, 0) + 1);16        }17 18        Arrays.sort(changed);19 20        int[] original = new int[n / 2];21        int index = 0;22 23        for (int num : changed) {24            if (freq.get(num) == 0) {25                continue;26            }27 28            freq.put(num, freq.get(num) - 1);29            int target = num * 2;30 31            if (freq.getOrDefault(target, 0) > 0) {32                freq.put(target, freq.get(target) - 1);33                original[index++] = num;34            } else {35                return new int[0];36            }37        }38 39        return original;40    }41}

Complexity

Time

O(N log N), where N is the length of `changed`. The sorting step is the most time-consuming part. Building the map and iterating through the sorted array both take O(N) time.

Space

O(N), where N is the length of `changed`. The space is used for the frequency map and the result array.

Trade-offs

Pros

Much more efficient than the brute-force approach, with O(N log N) complexity.
The logic is robust and handles various edge cases like zeros and duplicates correctly.
Works for any range of integer values.

Cons

The O(N log N) time complexity from sorting is the bottleneck.
Requires O(N) extra space for the hash map, which can be significant.

This is the most efficient approach, which is possible due to the problem's constraints on the range of values in the changed array. Instead of a general-purpose sort and hash map, we can use a frequency array (a specialized form of counting sort). We create an array to hold the counts of each number from 0 up to the maximum possible value. By iterating through this frequency array from smallest to largest, we can pair numbers with their doubles in linear time, avoiding the O(N log N) overhead of a comparison sort.

Algorithm

Check if the length of changed is odd. If so, return an empty array.
Given the constraint 0 <= changed[i] <= 10^5, create a frequency array counts of size 2 * 10^5 + 1.
Populate the counts array by iterating through changed and incrementing counts[num] for each number.
Initialize an original array of size N/2 and a result index k = 0.
Handle the special case of zero: if counts[0] is odd, return []. Otherwise, add counts[0] / 2 zeros to the original array.
Iterate from i = 1 up to 10^5.
- If counts[i] is greater than 0, it means we have counts[i] instances of the number i that must be from the original array (since we are iterating in increasing order).
- We need to find counts[i] instances of its double, 2*i.
- Check if counts[2*i] is less than counts[i]. If it is, we don't have enough doubles, so return [].
- If we have enough doubles, subtract counts[i] from counts[2*i] to mark them as used.
- Add the number i to the original array counts[i] times.
After the loop, if the number of elements added to original (k) is equal to N/2, return original. Otherwise, return [] (this handles leftover numbers that couldn't be paired).

Walkthrough

This method capitalizes on the constraint that 0 <= changed[i] <= 10^5. We can declare an integer array counts of size 2 * 10^5 + 1 to store the frequency of each number. We make a single pass through changed to populate this counts array. Then, we iterate through the counts array itself, from i = 0 to 10^5. This ordered iteration ensures we always process a number i before its double 2*i. For each i, if counts[i] is positive, we must find counts[i] corresponding doubles at index 2*i. We check if counts[2*i] has at least counts[i] elements. If not, the pairing is impossible, and we return an empty array. If it does, we add i to our result counts[i] times and decrement counts[2*i] by counts[i]. The case for i=0 is handled separately first: an odd count of zeros is invalid, otherwise, we pair them up. This approach achieves linear time complexity because we only make a few passes over the input array and the fixed-size counts array.

1class Solution {2    public int[] findOriginalArray(int[] changed) {3        int n = changed.length;4        if (n % 2 != 0) {5            return new int[0];6        }7 8        int[] counts = new int[200001];9        for (int num : changed) {10            counts[num]++;11        }12 13        int[] original = new int[n / 2];14        int k = 0;15 16        // Handle zeros17        if (counts[0] % 2 != 0) {18            return new int[0];19        }20        for (int i = 0; i < counts[0] / 2; i++) {21            original[k++] = 0;22        }23 24        for (int i = 1; i <= 100000; i++) {25            if (counts[i] > 0) {26                int target = i * 2;27                // Check if we have enough doubles28                if (counts[target] < counts[i]) {29                    return new int[0];30                }31                // Use the doubles32                counts[target] -= counts[i];33                // Add the original numbers to the result34                for (int j = 0; j < counts[i]; j++) {35                    original[k++] = i;36                }37            }38        }39 40        // If k is not n/2, it means there were leftover numbers that were not doubles of anything41        return k == n / 2 ? original : new int[0];42    }43}

Complexity

Time

O(N + K), where N is the length of `changed` and K is the maximum possible value (`10^5`). O(N) to build the frequency array and O(K) to iterate through it to find pairs. This is linear time.

Space

O(N + K), where N is the input size and K is the maximum possible value of an element (`10^5`). Space is required for the frequency array (`O(K)`) and the result array (`O(N)`).

Trade-offs

Pros

Optimal time complexity of O(N + K), which is linear.
Avoids the overhead of comparison sorting and hash map operations.

Cons

The space complexity is dependent on the maximum possible value in the input (K), not just the input size N. If K is very large, this approach becomes infeasible.
It is only applicable when the range of input values is known and reasonably small.

Solutions

Solution

1class Solution {2public3  int[] findOriginalArray(int[] changed) {4    int n = changed.length;5    if (n % 2 == 1) {6      return new int[]{};7    }8    Arrays.sort(changed);9    int[] cnt = new int[changed[n - 1] + 1];10    for (int x : changed) {11      ++cnt[x];12    }13    int[] ans = new int[n / 2];14    int i = 0;15    for (int x : changed) {16      if (cnt[x] == 0) {17        continue;18      }19      if (x * 2 >= cnt.length || cnt[x * 2] <= 0) {20        return new int[]{};21      }22      ans[i++] = x;23      cnt[x]--;24      cnt[x * 2]--;25    }26    return i == n / 2 ? ans : new int[]{};27  }28}

1class Solution {2public:3  vector<int> findOriginalArray(vector<int> &changed) {4    int n = changed.size();5    if (n & 1) {6      return {};7    }8    sort(changed.begin(), changed.end());9    vector<int> cnt(changed.back() + 1);10    for (int &x : changed) {11      ++cnt[x];12    }13    vector<int> ans;14    for (int &x : changed) {15      if (cnt[x] == 0) {16        continue;17      }18      if (x * 2 >= cnt.size() || cnt[x * 2] <= 0) {19        return {};20      }21      ans.push_back(x);22      --cnt[x];23      --cnt[x * 2];24    }25    return ans.size() == n / 2 ? ans : vector<int>();26  }27};

1class Solution:2    def findOriginalArray(self, changed: List[int]) -> List[int]: n = len(changed) if n & 1: return [] cnt = Counter(changed) changed . sort() ans = [] for x in changed: if cnt[x] == 0: continue if cnt[x * 2] <= 0: return [] ans . append(x) cnt[x] -= 1 cnt[x * 2] -= 1 return ans if len(ans) == n // 2 else []

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int[] findOriginalArray(int[] changed) {4    int n = changed.length;5    if (n % 2 == 1) {6      return new int[]{};7    }8    Arrays.sort(changed);9    int[] cnt = new int[changed[n - 1] + 1];10    for (int x : changed) {11      ++cnt[x];12    }13    int[] ans = new int[n / 2];14    int i = 0;15    for (int x : changed) {16      if (cnt[x] == 0) {17        continue;18      }19      if (x * 2 >= cnt.length || cnt[x * 2] <= 0) {20        return new int[]{};21      }22      ans[i++] = x;23      cnt[x]--;24      cnt[x * 2]--;25    }26    return i == n / 2 ? ans : new int[]{};27  }28}

1class Solution {2public:3  vector<int> findOriginalArray(vector<int> &changed) {4    int n = changed.size();5    if (n & 1) {6      return {};7    }8    sort(changed.begin(), changed.end());9    vector<int> cnt(changed.back() + 1);10    for (int &x : changed) {11      ++cnt[x];12    }13    vector<int> ans;14    for (int &x : changed) {15      if (cnt[x] == 0) {16        continue;17      }18      if (x * 2 >= cnt.size() || cnt[x * 2] <= 0) {19        return {};20      }21      ans.push_back(x);22      --cnt[x];23      --cnt[x * 2];24    }25    return ans.size() == n / 2 ? ans : vector<int>();26  }27};

1class Solution:2    def findOriginalArray(self, changed: List[int]) -> List[int]: n = len(changed) if n & 1: return [] cnt = Counter(changed) changed . sort() ans = [] for x in changed: if cnt[x] == 0: continue if cnt[x * 2] <= 0: return [] ans . append(x) cnt[x] -= 1 cnt[x * 2] -= 1 return ans if len(ans) == n // 2 else []

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.