Problem Statement
Given an integer array changed, which contains 2n elements, where each element in some original array original and its double appear in the changed array, return the original array. If the changed array cannot be a valid doubled array, return an empty array.
Examples
Example 1:
Input: changed = [1, 3, 4, 2, 6, 8]
Output: [1, 3, 4]
Explanation: The elements [2, 6, 8] are doubled of the element [1, 3, 4]Example 2:
Input: changed = [6, 3, 0, 1]
Output: []
Explanation: 6 is double of 3 however, 0 and 1 and not related anyhow, so return empty array.Different Approaches
1️⃣ Hashing
Approach:
- Sort the array: The first step is to sort the
changedarray. This allows us to process smaller numbers before their doubles, making it easier to match pairs. - Use a frequency map: Use a frequency map (hash map) to count occurrences of each element in the
changedarray. For each elementx, try to find its double2 * xin the map. - Process each element:
- For each element
xin the sortedchangedarray:- If
xis already used (i.e., its frequency is0), skip it. - Check if there is a
2 * xavailable in the frequency map. If not, the array is invalid. - Decrement the count of
xand2 * xin the map, and addxto the original array.
- If
- For each element
- Edge case: If there are odd numbers of zeros in the array, it’s invalid since you can't form pairs.
Dry Run:
Initialization:
+-----+-----+-----+-----+-----+-----+
changed = | 1 | 3 | 4 | 2 | 6 | 8 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5Sort the array:
+-----+-----+-----+-----+-----+-----+
changed = | 1 | 2 | 3 | 4 | 6 | 8 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5Store the frequencies of each element in a map:
+-----+-----+-----+-----+-----+-----+
changed = | 1 | 2 | 3 | 4 | 6 | 8 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
map = key value
+-----+-----+
| 1 | 1 |
+-----+-----+
| 2 | 1 |
+-----+-----+
| 3 | 1 |
+-----+-----+
| 4 | 1 |
+-----+-----+
| 6 | 1 |
+-----+-----+
| 8 | 1 |
+-----+-----+Process each element
First Iteration:
+-----+-----+-----+-----+-----+-----+
changed = | 1 | 2 | 3 | 4 | 6 | 8 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
i
map = key value
+-----+-----+
| 1 | 1 |
+-----+-----+
| 2 | 1 |
+-----+-----+
| 3 | 1 |
+-----+-----+
| 4 | 1 |
+-----+-----+
| 6 | 1 |
+-----+-----+
| 8 | 1 |
+-----+-----+
+-----+
result = | |
+-----+
Check if changed[i]'s count is zero in map, meaning it is already processed (it is double of someone's).
False
Check if the double of changed[i]'s exist in map or not.
1*2 = 2, Yes it do exists.
Push changed[i] in the result vector, decrement the frequency count
of changed[i] and its double from the map.Second Iteration:
+-----+-----+-----+-----+-----+-----+
changed = | 1 | 2 | 3 | 4 | 6 | 8 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
i
map = key value
+-----+-----+
| 1 | 0 |
+-----+-----+
| 2 | 0 |
+-----+-----+
| 3 | 1 |
+-----+-----+
| 4 | 1 |
+-----+-----+
| 6 | 1 |
+-----+-----+
| 8 | 1 |
+-----+-----+
+-----+
result = | 1 |
+-----+
Check if changed[i]'s count is zero in map, meaning it is already processed (it is double of someone's).
True, Continue to the next iteration.Third Iteration:
+-----+-----+-----+-----+-----+-----+
changed = | 1 | 2 | 3 | 4 | 6 | 8 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
i
map = key value
+-----+-----+
| 1 | 0 |
+-----+-----+
| 2 | 0 |
+-----+-----+
| 3 | 1 |
+-----+-----+
| 4 | 1 |
+-----+-----+
| 6 | 1 |
+-----+-----+
| 8 | 1 |
+-----+-----+
+-----+
result = | 1 |
+-----+
Check if changed[i]'s count is zero in map, meaning it is already processed (it is double of someone's).
False
Check if the double of changed[i]'s exist in map or not.
3*2 = 6, Yes it do exists.
Push changed[i] in the result vector, decrement the frequency count
of changed[i] and its double from the map.Fourth Iteration:
+-----+-----+-----+-----+-----+-----+
changed = | 1 | 2 | 3 | 4 | 6 | 8 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
i
map = key value
+-----+-----+
| 1 | 0 |
+-----+-----+
| 2 | 0 |
+-----+-----+
| 3 | 0 |
+-----+-----+
| 4 | 1 |
+-----+-----+
| 6 | 0 |
+-----+-----+
| 8 | 1 |
+-----+-----+
+-----+-----+
result = | 1 | 3 |
+-----+-----+
Check if changed[i]'s count is zero in map, meaning it is already processed (it is double of someone's).
False
Check if the double of changed[i]'s exist in map or not.
4*2 = 8, Yes it do exists.
Push i in the result vector, decrement the frequency count
of i and its double from the map.Fifth Iteration:
+-----+-----+-----+-----+-----+-----+
changed = | 1 | 2 | 3 | 4 | 6 | 8 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
i
map = key value
+-----+-----+
| 1 | 0 |
+-----+-----+
| 2 | 0 |
+-----+-----+
| 3 | 0 |
+-----+-----+
| 4 | 0 |
+-----+-----+
| 6 | 0 |
+-----+-----+
| 8 | 0 |
+-----+-----+
+-----+-----+-----+
result = | 1 | 3 | 4 |
+-----+-----+-----+
Check if i's count is zero in map, meaning it is already processed (it is
double of someone's).
True, Continue to the next iteration.Sixth Iteration:
+-----+-----+-----+-----+-----+-----+
changed = | 1 | 2 | 3 | 4 | 6 | 8 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
i
map = key value
+-----+-----+
| 1 | 0 |
+-----+-----+
| 2 | 0 |
+-----+-----+
| 3 | 0 |
+-----+-----+
| 4 | 0 |
+-----+-----+
| 6 | 0 |
+-----+-----+
| 8 | 0 |
+-----+-----+
+-----+-----+-----+
result = | 1 | 3 | 4 |
+-----+-----+-----+
Check if i's count is zero in map, meaning it is already processed (it is
double of someone's).
True, Continue to the next iteration.Code:
Using for each loop:
vector<int> findOriginalArray(vector<int>& changed) {
if (changed.size() % 2 != 0) {
// If the length of the changed array is odd, return an empty array
return {};
}
// Step 1: Sort the array
sort(changed.begin(), changed.end());
// Step 2: Create a frequency map
unordered_map<int, int> freq;
for (int num : changed) {
freq[num]++;
}
vector<int> original;
// Step 3: Process each element in the sorted changed array
for (int num : changed) { // Corrected: Iterate over elements, not indices
if (freq[num] == 0) {
// If num is already used, skip it
continue;
}
if (freq[num * 2] == 0) {
// If the double of num does not exist, return empty array
return {};
}
// Add num to the original array
original.push_back(num);
// Decrement the frequency of num and its double
freq[num]--;
freq[num * 2]--;
}
return original;
}
Using Simple for loop:
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
vector<int> findOriginalArray(vector<int>& changed) {
if (changed.size() % 2 != 0) {
// If the length of the changed array is odd, return an empty array
return {};
}
// Step 1: Sort the array
sort(changed.begin(), changed.end());
// Step 2: Create a frequency map
unordered_map<int, int> freq;
for (int num : changed) {
freq[num]++;
}
vector<int> original;
// Step 3: Process each element
for (int num = 0; num < changed.size(); num++) {
if (freq[changed[num]] == 0) {
// If num is already used, skip it
continue;
}
if (freq[changed[num] * 2] == 0) {
// If the double of num does not exist, return empty array
return {};
}
// Add num to the original array
original.push_back(changed[num]);
// Decrement the frequency of num and its double
freq[changed[num]]--;
freq[changed[num] * 2]--;
}
return original;
}
int main() {
vector<int> changed = {0, 0, 0, 0};
vector<int> original = findOriginalArray(changed);
// Output the original array
if (!original.empty()) {
for (int num : original) {
cout << num << " ";
}
} else {
cout << "[]"; // If no valid original array, output empty array
}
return 0;
}
Complexity Analysis:
- Time Complexity:
- Sorting the array:
O(n log n). - Building the frequency map:
O(n). - Processing elements:
O(n)since we traverse the array once. - The overall time complexity is O(n log n) due to the sorting step.
- Sorting the array:
- Space Complexity:
- O(n) for the frequency map and the original array.