Find Original Array From Doubled Array
MedPrompt
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] <= 105
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
changedarray is odd. If it is, it cannot be a doubled array, so return an empty array. - Sort the
changedarray in non-decreasing order. - Create a boolean array
usedof the same size aschanged, initialized tofalse, to keep track of numbers that have been paired. - Initialize an empty list
originalto store the result. - Iterate through the sorted
changedarray from left to right. - For each element
numat indexi:- If
used[i]istrue, it means this number has already been used as a double for a smaller number, so skip it. - Mark
used[i]astrueand addnumto theoriginallist. - Perform a linear search for
num * 2in the rest of the array (from indexi + 1). - If an unused
num * 2is found at indexj, markused[j]astrueand stop the search for thisnum. - If an unused
num * 2is not found, it meanschangedis not a valid doubled array. Return an empty array.
- If
- If the loop completes successfully, the
originallist 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.
import java.util.ArrayList;import java.util.Arrays;import java.util.List; class Solution { public int[] findOriginalArray(int[] changed) { int n = changed.length; if (n % 2 != 0) { return new int[0]; } Arrays.sort(changed); List<Integer> originalList = new ArrayList<>(); boolean[] used = new boolean[n]; int count = 0; for (int i = 0; i < n; i++) { if (used[i]) { continue; } int num = changed[i]; int target = num * 2; boolean found = false; for (int j = i + 1; j < n; j++) { if (!used[j] && changed[j] == target) { used[j] = true; found = true; break; } } if (found) { originalList.add(num); count++; } else { return new int[0]; } } if (count != n / 2) { return new int[0]; } return originalList.stream().mapToInt(i -> i).toArray(); }}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.
Solutions
Solution
class Solution {public int[] findOriginalArray(int[] changed) { int n = changed.length; if (n % 2 == 1) { return new int[]{}; } Arrays.sort(changed); int[] cnt = new int[changed[n - 1] + 1]; for (int x : changed) { ++cnt[x]; } int[] ans = new int[n / 2]; int i = 0; for (int x : changed) { if (cnt[x] == 0) { continue; } if (x * 2 >= cnt.length || cnt[x * 2] <= 0) { return new int[]{}; } ans[i++] = x; cnt[x]--; cnt[x * 2]--; } return i == n / 2 ? ans : new int[]{}; }}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.