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 <= 1050 <= changed[i] <= 105In #2007 Find Original Array From Doubled Array, you are given an array that was created by taking an original array, appending each element’s double, and then shuffling the result. The challenge is to reconstruct the original array or determine that it is impossible.
A common strategy combines sorting with a hash table (frequency map). By sorting the array first, you can process numbers from smallest to largest and ensure that when you encounter a number x, you can check whether its doubled value 2 * x exists. A frequency map helps track how many times each number still needs to be paired. If the count of 2 * x is insufficient, reconstruction is impossible.
This greedy pairing approach ensures each number is matched with its double exactly once. Care must be taken with values like 0 and negative numbers, where ordering and counts matter. The overall process is efficient because sorting dominates the runtime.
Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) for the frequency map and result array.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting + Hash Map (Greedy Pairing) | O(n log n) | O(n) |
| Frequency Counting with Ordered Processing | O(n log n) | O(n) |
codestorywithMIK
Use these hints if you're stuck. Try solving on your own first.
If changed is a doubled array, you should be able to delete elements and their doubled values until the array is empty.
Which element is guaranteed to not be a doubled value? It is the smallest element.
After removing the smallest element and its double from changed, is there another number that is guaranteed to not be a doubled value?
This approach utilizes a hash map to count occurrences of elements and sorting to efficiently find element pairs. First, the input array is sorted, and then iteratively each element is processed to find its double using the hash map. If a valid pair is found, both are adjusted accordingly in the map to avoid reuse. If at the end the map ends up having unprocessed values, it indicates that the array cannot form a doubled array, thus returning an empty array.
Time Complexity: O(n log n) due to sorting and O(n) for iterating, total O(n log n).
Space Complexity: O(n) for the hash map.
1def findOriginalArray(changed):
2 if len(changed) % 2 != 0:
3 return [] # Cannot form pairs if length is odd
4 from collections import Counter
5 changed.sort()
6 count = Counter(changed)
7 original = []
8 for x in changed:
9 if count[x] == 0:
10 continue
11 if count[2 * x] == 0:
12 return []
13 original.append(x)
14 count[x] -= 1
15 count[2 * x] -= 1
16 return originalThis Python solution sorts the changed array and uses a hash map (via Counter) to count frequencies. It finds pairs by iterating sorted numbers and adjusts counts making sure each number and its double are in the count. If a match isn't found during iteration, it returns an empty list.
This approach uses a two-point strategy over a sorted array to match each number with its double. Start two pointers: the first at the beginning and the second just after it. Iterate through the array attempting to pair the number at the first pointer with its double at the second pointer. Valid pairs are those which multiply perfectly and do not leave remainder elements. Return an empty array if any mismatch occurs.
Time Complexity: O(n log n) due to sorting and O(n) for the pairing process, total O(n log n).
Space Complexity: O(n) due to the counting object.
1function findOriginalArray(changed) {
2Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Sorting ensures that smaller numbers are processed first, which prevents incorrect pairings. This is especially important because once a number is used to match with its double, its count must be updated before moving forward.
Yes, variations of this problem appear in coding interviews at large tech companies. It tests understanding of greedy strategies, hash maps, and careful handling of edge cases like zero or negative values.
A hash table or frequency map is the most useful data structure for this problem. It allows you to efficiently track how many times each value appears and verify whether a corresponding doubled value is available.
The optimal approach uses sorting combined with a hash map (frequency counter). By sorting the array and pairing each number with its double, you can greedily reconstruct the original array while tracking counts to ensure valid matches.
This JavaScript solution relies on counting occurrences using an object and tries to find each element's double in a sorted array. If a match cannot be found, an empty array is returned. Otherwise, it builds the original array as it iterates.