Leetcode 2007: Find Original Array From Doubled Array
You are given an array changed, which may have been created by doubling each element of an original array and then shuffling the elements. Your task is to determine if changed can be converted back into the original array, where each element in the original array has its double present in changed. If changed is not a valid doubled array, return an empty array. If it is valid, return the original array.
Problem
Approach
Steps
Complexity
Input: The input consists of an array changed, which may be a shuffled version of the original array with each element doubled.
Example: changed = [2, 4, 1, 8, 3, 6]
Constraints:
• 1 <= changed.length <= 10^5
• 0 <= changed[i] <= 10^5
Output: Return the original array if it is valid, otherwise return an empty array.
Example: [1, 3, 4]
Constraints:
Goal: The goal is to check whether each element in changed has its double also in changed and return the original array or an empty array if it is not possible.
Steps:
• 1. Check if the size of changed is even, as there must be pairs of elements.
• 2. Sort the array to easily identify and pair the elements.
• 3. Use a frequency map to count occurrences of each element in changed.
• 4. For each element, check if its double exists in the map and decrease the counts accordingly.
• 5. Return the original array if all pairs are valid, otherwise return an empty array.
Goal: The input array is between 1 and 100,000 elements long, with values ranging from 0 to 100,000 for each element.
Steps:
• 1 <= changed.length <= 10^5
• 0 <= changed[i] <= 10^5
Assumptions:
• The solution should efficiently handle arrays of size up to 100,000.
• Handling large numbers and ensuring correctness of doubled pairs is critical.
• Input: changed = [2, 4, 1, 8, 3, 6]
• Explanation: The valid pairs are (1, 2), (3, 6), and (4, 8). Hence, the original array is [1, 3, 4].
• Input: changed = [3, 0, 1, 6]
• Explanation: Since there are no valid pairs, the output is an empty array.
• Input: changed = [5]
• Explanation: Since there is no pair for 5, the output is an empty array.
Approach: To solve this problem efficiently, we can use a frequency map to track the counts of each number in the array and validate if each element has its double present.
Observations:
• We need to ensure that for each element in the array, its double exists in the array as well.
• Sorting the array and using a frequency map will help efficiently check if the doubled elements exist.
Steps:
• 1. Sort the input array.
• 2. Count the frequency of each element using a map.
• 3. For each element, check if its double exists in the map and reduce the count.
• 4. If any element doesn't have its double, return an empty array.
• 5. Return the original array after processing.
Empty Inputs:
• If the array has an odd number of elements, return an empty array.
Large Inputs:
• Ensure that the algorithm runs efficiently for arrays with the maximum size of 100,000.
Special Values:
• If the array contains 0, ensure it pairs correctly with another 0.
Constraints:
• Ensure the solution works within the given constraints of 1 <= changed.length <= 10^5 and 0 <= changed[i] <= 10^5.
vector<int> findOriginalArray(vector<int>& chg) {
if(chg.size() % 2) return vector<int>{};
sort(chg.begin(), chg.end());
map<int, int> mp;
for(int i = 0; i < chg.size(); i++)
mp[chg[i]]++;
vector<int> ans;
int i = 0;
while((ans.size() < chg.size() / 2) && i < chg.size()) {
if(chg[i] == 0) {
if(mp[chg[i]] >= 2) {
mp[chg[i]] -= 2;
ans.push_back(chg[i]);
}
i++;
continue;
}
if((mp.count(chg[i]) && mp.count(chg[i] * 2))) {
ans.push_back(chg[i]);
if(mp[chg[i]] == 1)
mp.erase(chg[i]);
else
mp[chg[i]]--;
if(mp[chg[i] * 2] == 1)
mp.erase(chg[i] * 2);
else
mp[chg[i] * 2]--;
// cout << chg[i] << " " << mp[chg[i] ] << "\n";
// cout << chg[i] * 2 << " " << mp[chg[i] * 2] << "\n";
}
i++;
}
return ans.size() == chg.size() / 2? ans: vector<int>{};
}
1 : Function Definition
vector<int> findOriginalArray(vector<int>& chg) {
Defines the function `findOriginalArray` which accepts a reference to a vector `chg` and returns the original array if possible.
2 : Odd Size Check
if(chg.size() % 2) return vector<int>{};
Checks if the size of the `chg` array is odd. If so, it returns an empty vector since the original array cannot be formed.
3 : Sorting
sort(chg.begin(), chg.end());
Sorts the array `chg` in ascending order to ensure elements are processed in a sequential manner.
4 : Frequency Map Setup
map<int, int> mp;
Declares a map `mp` to store the frequency of each element in `chg`.
5 : Counting Frequency
for(int i = 0; i < chg.size(); i++)
Iterates through each element in the sorted `chg` array to count its frequency.
6 : Increment Frequency
mp[chg[i]]++;
Increments the count of the current element `chg[i]` in the frequency map `mp`.
7 : Original Array Setup
vector<int> ans;
Declares a vector `ans` to store the elements of the original array once identified.
8 : Index Initialization
int i = 0;
Initializes the index `i` to iterate through the sorted `chg` array.
9 : Loop Condition Check
while((ans.size() < chg.size() / 2) && i < chg.size()) {
Starts a while loop that continues until half of the elements are found in `ans` or until all elements have been processed.
10 : Zero Check
if(chg[i] == 0) {
Checks if the current element is zero.
11 : Zero Pairing
if(mp[chg[i]] >= 2) {
If the count of zero is at least 2, it is valid for pairing.
12 : Update Map for Zero
mp[chg[i]] -= 2;
Decreases the count of zero by 2 in the frequency map since it forms a valid pair.
13 : Store Zero in Answer
ans.push_back(chg[i]);
Adds zero to the result array `ans`.
14 : Continue Check
i++;
Increments the index `i` to continue checking the next element.
15 : Skip to Next
continue;
Skips the rest of the loop and continues to the next iteration.
16 : Pair Check for Non-Zero
if((mp.count(chg[i]) && mp.count(chg[i] * 2))) {
Checks if the current element `chg[i]` and its double `chg[i]*2` are both present in the map `mp`.
17 : Store Element in Answer
ans.push_back(chg[i]);
Adds the current element `chg[i]` to the result array `ans`.
18 : Erase or Decrement Map
if(mp[chg[i]] == 1)
Checks if the frequency of `chg[i]` is 1.
19 : Remove Element from Map
mp.erase(chg[i]);
Removes the element `chg[i]` from the map `mp`.
20 : Decrement Frequency
else
mp[chg[i]]--;
If there are more than one of `chg[i]`, it decrements its frequency.
21 : Second Element Pair Check
if(mp[chg[i] * 2] == 1)
Checks if the frequency of `chg[i] * 2` is 1.
22 : Erase Second Element
mp.erase(chg[i] * 2);
Removes the doubled element from the frequency map.
23 : Decrement Second Element
else
mp[chg[i] * 2]--;
Decrements the frequency of `chg[i] * 2`.
24 : Increment Index
i++;
Increments the index `i` to continue checking the next element.
25 : Final Check
return ans.size() == chg.size() / 2? ans: vector<int>{};
Returns the result array `ans` if it contains half the size of the original array, otherwise returns an empty vector.
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)
Description: The time complexity is O(n log n) due to sorting the array, followed by a linear scan for checking pairs.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the use of a frequency map for counting elements.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus