2007. Find Original Array From Doubled Array
Problem Description
This problem provides an array called changed
, which has been created by taking an original array of integers, doubling each element, appending these doubled numbers to the original array, and then shuffling the entire collection of numbers.
Our task is to reconstruct the original array from the changed
array. However, there are some constraints:
- If the
changed
array has an odd number of elements, it's impossible to obtain the original array since doubling each element of the original array and then merging would result in an even number of total elements. - For each element in the
original
array, there must be a corresponding element inchanged
that is double its value. - If
changed
does not satisfy the property of being a "doubled array,” as described, we need to return an empty array.
We are allowed to return the elements of the original
array in any order, adding flexibility to our solution.
Intuition
To find the solution, the following intuition can guide us:
-
Sorting: We start by sorting
changed
since this will arrange all double elements after their corresponding originals (since 2 * x > x for all x > 0). Sorting also helps us to handle duplicates effectively. -
Counting: Using a counter (frequency map) over the sorted
changed
array helps in keeping track of the elements we've used for forming theoriginal
array and the elements that need to be paired with their doubles. -
Pairing and Elimination: We iterate over the sorted
changed
array and look for the double of each element. If for any elementx
, the element2x
does not exist in sufficient quantity (or does not exist at all), we cannot form theoriginal
array, hence, we return an empty array. -
Building the Original Array: If an element
x
and its double2x
are found, we pair them and reduce their count in the frequency map. The elementx
is added to theoriginal
array. -
Validation: In the end, if the generated
original
array has exactly half the length of thechanged
array, we have successfully reformed theoriginal
array. Otherwise, thechanged
array wasn't a doubled array, to begin with, or we couldn't pair all elements correctly, and we return an empty array.
Using this approach caters to all conditions provided in the problem, thus guaranteeing a correct solution when one is possible.
Solution Approach
The implementation follows the intuition closely using Python's built-in data structures and sorting algorithm.
Here's the step-by-step breakdown of the solution approach:
-
Check for the Odd Number of Elements: A quick check to confirm if the length of the
changed
array is odd. Since the doubled array should be even in length, return an empty array immediately if this is the case.1n = len(changed) 2if n & 1: 3 return []
-
Use a Counter for Frequency Tracking: A
Counter
object from thecollections
module is utilized to keep a frequency map of the elements inchanged
.1cnt = Counter(changed)
-
Sort the
changed
Array: Thechanged
array is sorted to ensure that the elements and their doubles are aligned in increasing order.1changed.sort()
-
Iterate to Build the
original
Array: A for-loop iterates over each element in the sortedchanged
array, applying the following logic:- Skip Processed Elements: If an element
x
has already been used (i.e., its count is 0), skip it.1if cnt[x] == 0: 2 continue
- Check for Double's Existence: If there is not enough of the double of
x
remaining (i.e.,cnt[2 * x]
is 0 or negative), thechanged
cannot be a doubled array, so return an empty list.1if cnt[x * 2] <= 0: 2 return []
- Add Element to
original
and Update Counts: If a valid double is found, appendx
to theoriginal
array and decrement the counts forx
and2 * x
.1ans.append(x) 2cnt[x] -= 1 3cnt[x * 2] -= 1
- Skip Processed Elements: If an element
-
Final Validation and Return: After the loop is done, check if the length of the
original
array is exactly half thechanged
array (which implies each element was paired correctly). If not, thechanged
array couldn't have been a doubled array, and thus, return an empty array.1return ans if len(ans) == n // 2 else []
By utilizing a sorted array and a frequency map, the algorithm ensures that all elements can be paired with their corresponding doubles, maintaining linearithmic time complexity due to sorting, with the remainder of operations being linear within the sorted array. The space complexity is linear due to the extra space used for the Counter
and the resulting original
array.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Suppose we have the following changed
array:
1changed = [1, 3, 4, 2, 6, 8]
Step-by-step, we perform the following actions:
-
Check for Odd Number of Elements: The length of the
changed
array is 6, which is even. We can proceed. -
Use a Counter for Frequency Tracking: Generate a frequency map:
1cnt = Counter([1, 3, 4, 2, 6, 8]) # Counter({1: 1, 3: 1, 2: 1, 4: 1, 6: 1, 8: 1})
-
Sort the
changed
Array: The sortedchanged
array looks like this:1changed = [1, 2, 3, 4, 6, 8]
-
Iterate to Build the
original
Array:-
For the first element
1
, we find that its double2
exists, so we add1
tooriginal
and update the counts:1ans = [1] 2cnt = {1: 0, 3: 1, 2: 0, 4: 1, 6: 1, 8: 1}
-
We skip
2
since its count is now0
. -
Next, for
3
, we find its double6
, add3
tooriginal
, and update counts:1ans = [1, 3] 2cnt = {1: 0, 3: 0, 2: 0, 4: 1, 6: 0, 8: 1}
-
We skip
4
as we don't have8
(double of4
) in enough quantity (count is0
), and since we can't find a valid double, we would normally return an empty array. However, for demonstration purposes, we will assume the double8
exists and continue:1ans = [1, 3, 4] 2cnt = {1: 0, 3: 0, 2: 0, 4: 0, 6: 0, 8: 0}
-
-
Final Validation and Return: Now
ans
has 3 elements, which is half of thechanged
array's length. Therefore, assuming that a double for each element existed, ouroriginal
array is[1, 3, 4]
.
This simplified example demonstrates how each step logically brings us closer to the reconstructed original
array or leads us to conclude that reconstruction is not possible if the conditions are not met.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def findOriginalArray(self, changed: List[int]) -> List[int]:
5 # Get the length of the array
6 n = len(changed)
7 # If the length of the array is odd, we cannot form a doubled array
8 if n % 2 == 1:
9 return []
10 # Count the frequency of each element in the array
11 element_counter = Counter(changed)
12 # Sort the array to handle pairs in ascending order
13 changed.sort()
14 # Initialize the original array
15 original_array = []
16
17 # Iterate over the sorted array
18 for number in changed:
19 # Skip the number if it has already been paired
20 if element_counter[number] == 0:
21 continue
22 # If there isn't a double of this number, we can't form a valid array
23 if element_counter[number * 2] <= 0:
24 return []
25 # Add the number to the original array and adjust the counts for the number and its double
26 original_array.append(number)
27 element_counter[number] -= 1
28 element_counter[number * 2] -= 1
29
30 # Return the original array only if it is half the size of the changed array; otherwise, return an empty array
31 return original_array if len(original_array) == n // 2 else []
32
33# Here is the correct usage of list and typing import for the List type annotation
34from typing import List
35
1import java.util.Arrays;
2
3class Solution {
4 public int[] findOriginalArray(int[] changed) {
5 // Find the length of the changed array
6 int length = changed.length;
7
8 // if the length is odd, there cannot be an original array
9 // because the original and double elements aren't in pairs
10 if (length % 2 == 1) {
11 return new int[0];
12 }
13
14 // Sort the array to ensure the paired items can be found easily
15 Arrays.sort(changed);
16
17 // Initialize the count array to keep track of the frequency of each number
18 int[] frequency = new int[changed[length - 1] + 1];
19 for (int num : changed) {
20 frequency[num]++;
21 }
22
23 // Initialize the resulting array with half the length of the changed array
24 int[] result = new int[length / 2];
25 int resultIndex = 0;
26
27 // Go through the elements in changed array to find the original numbers
28 for (int num : changed) {
29 // Skip already paired numbers
30 if (frequency[num] == 0) {
31 continue;
32 }
33 // If the double value is out of the frequency array's range or already used up
34 if (num * 2 >= frequency.length || frequency[num * 2] <= 0) {
35 return new int[0];
36 }
37 // If a valid pair is found, put it in the result
38 result[resultIndex++] = num;
39 // Decrement the counts for the number and its double
40 frequency[num]--;
41 frequency[num * 2]--;
42 }
43
44 // Check if we've successfully found the original array
45 return resultIndex == length / 2 ? result : new int[0];
46 }
47}
48
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 vector<int> findOriginalArray(vector<int>& changed) {
7 int n = changed.size();
8
9 // If the size is odd, it's impossible to form an original array
10 if (n % 2 != 0) {
11 return {};
12 }
13
14 // Sort the array to make sure that for every element x, x*2 comes after x if it exists
15 sort(changed.begin(), changed.end());
16
17 // Create a frequency array that accounts for all elements in 'changed'
18 vector<int> frequency(changed.back() + 1, 0);
19 for (int x : changed) {
20 frequency[x]++;
21 }
22
23 // Initialize the vector to store the original array elements
24 vector<int> originalArray;
25
26 // Iterate over the sorted 'changed' array
27 for (int x : changed) {
28 if (frequency[x] == 0) {
29 // If the current element's count is already 0, skip it
30 continue;
31 }
32
33 if (x * 2 >= frequency.size() || frequency[x * 2] <= 0) {
34 // If there are no elements double the current or outside of the count range, return empty
35 return {};
36 }
37
38 // Decrement the count of the element and its double
39 originalArray.push_back(x);
40 frequency[x]--;
41 frequency[x * 2]--;
42 }
43
44 // If the size of formed originalArray is exactly half of the 'changed' array, return it
45 // Otherwise, return an empty vector indicating no valid original array could be formed
46 return originalArray.size() == n / 2 ? originalArray : vector<int>();
47 }
48};
49
1function findOriginalArray(changed: number[]): number[] {
2 // Check if the array length is odd; if so, there can't be an original array
3 const length = changed.length;
4 if (length % 2 !== 0) {
5 return [];
6 }
7
8 // Create a map to count occurrences of each number
9 const frequencyCounter = new Map<number, number>();
10
11 // Populate the frequency counter with the frequency of each number
12 for (const number of changed) {
13 frequencyCounter.set(number, (frequencyCounter.get(number) || 0) + 1);
14 }
15
16 // Sort the array to process pairs in order
17 changed.sort((a, b) => a - b);
18
19 // Initialize an array to store the original array
20 const originalArray: number[] = [];
21
22 // Iterate through the sorted array to find and validate pairs
23 for (const number of changed) {
24 // If the current number is already processed, skip it
25 if (frequencyCounter.get(number) === 0) {
26 continue;
27 }
28
29 // If there is no valid pair for the current number, return an empty array
30 if ((frequencyCounter.get(number * 2) || 0) <= 0) {
31 return [];
32 }
33
34 // Add the current number to the original array
35 originalArray.push(number);
36
37 // Decrement the frequency of the current number and its pair
38 frequencyCounter.set(number, frequencyCounter.get(number)! - 1);
39 frequencyCounter.set(number * 2, frequencyCounter.get(number * 2)! - 1);
40 }
41
42 // If the original array's length is half of the changed array, return it; otherwise, return an empty array
43 return originalArray.length * 2 === length ? originalArray : [];
44}
45
Time and Space Complexity
Time Complexity
The time complexity of the provided code can be broken down as follows:
- Getting the length of
changed
(n = len(changed)
) is anO(1)
operation. - Checking for even length (
if n & 1
) is also anO(1)
operation. - Creating a counter (
cnt = Counter(changed)
) counts the frequency of each number inchanged
, which is anO(n)
operation. - Sorting the array (
changed.sort()
) takesO(n log n)
time. - The loop runs through the sorted list of numbers (
for x in changed
). In the worst case, it runsn
times. Each operation inside isO(1)
because accessing and modifying the counter is constant time, given a good hash function. - Condition checks inside the loop and counter updates are all
O(1)
. - The last return statement (
return ans if len(ans) == n // 2 else []
) is anO(1)
operation.
The most time-consuming steps are the counter creation and the sorting. Adding the complexities, we get:
O(n)
(for counting) + O(n log n)
(for sorting) + O(n)
(for iterating through the list) = O(n log n)
.
Therefore, the overall time complexity of the algorithm is O(n log n)
.
Space Complexity
For space complexity:
- Additional space is used to store the counter (
cnt
), which can be up toO(n)
if all numbers are unique. - Space for the output array (
ans
), which is half of the input array's size in the best case, soO(n/2)
simplifies toO(n)
.
Hence, the overall space complexity of the algorithm is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following problems can be solved with backtracking (select multiple)
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear? Submit the part you don't understand to our editors. Or join our Discord and ask the community.