2007. Find Original Array From Doubled Array LeetCode Solution
In this guide, you will get 2007. Find Original Array From Doubled Array LeetCode Solution with the best time and space complexity. The solution to Find Original Array From Doubled Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find Original Array From Doubled Array
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.
2007. Find Original Array From Doubled Array LeetCode Solution in C++
class Solution {
public:
vector<int> findOriginalArray(vector<int>& changed) {
vector<int> ans;
queue<int> q;
ranges::sort(changed);
for (const int num : changed)
if (!q.empty() && num == q.front()) {
q.pop();
} else {
q.push(num * 2);
ans.push_back(num);
}
return q.empty() ? ans : vector<int>();
}
}; /* code provided by PROGIEZ */
2007. Find Original Array From Doubled Array LeetCode Solution in Java
class Solution {
public int[] findOriginalArray(int[] changed) {
List<Integer> ans = new ArrayList<>();
Queue<Integer> q = new ArrayDeque<>();
Arrays.sort(changed);
for (final int num : changed)
if (!q.isEmpty() && num == q.peek()) {
q.poll();
} else {
q.offer(num * 2);
ans.add(num);
}
return q.isEmpty() ? ans.stream().mapToInt(Integer::intValue).toArray() : new int[] {};
}
} // code provided by PROGIEZ
2007. Find Original Array From Doubled Array LeetCode Solution in Python
class Solution:
def findOriginalArray(self, changed: list[int]) -> list[int]:
ans = []
q = collections.deque()
for num in sorted(changed):
if q and num == q[0]:
q.popleft()
else:
q.append(num * 2)
ans.append(num)
return [] if q else ans # code by PROGIEZ
