2007. Find Original Array From Doubled Array
https://leetcode.com/problems/find-original-array-from-doubled-array/
Python
Straightforward solution (Time limit exceed)
class Solution:
def findOriginalArray(self, changed: List[int]) -> List[int]:
changed.sort()
origin, cand = [], []
temp = []
# Odd number can't possible be the doubled, filter them and early return
for num in changed:
if num % 2 == 0:
cand.append(num)
else:
origin.append(num)
for num in origin:
if cand and num*2 in cand:
cand.pop(cand.index(num*2))
else:
return []
# Process the remains
for i in range(len(cand)):
num = cand[i]
if num == -1:
continue
elif num != -1:
cand[i] = -1
if num*2 in cand:
origin.append(num)
cand[cand.index(num*2)] = -1
else:
return []
else:
return []
cand = [n for n in cand if n != -1]
return [] if cand else origin
Solution from tanmaysankhe
class Solution:
def findOriginalArray(self, changed: List[int]) -> List[int]:
#sorting the input array
changed.sort()
i = 0
ans = []
#dict for maintaining double of current element
doubled = collections.defaultdict(int)
while i < len(changed):
#checking if the current element is double of other element, if yes then skipping the element
if doubled[changed[i]] > 0:
doubled[changed[i]] -= 1
i += 1
continue
#adding element to ans and it's double in the dictionary
ans.append(changed[i])
doubled[changed[i]*2] += 1
i += 1
#if dictionary have values other than 0 means there were someelements whose double were not in the changed list
for i in doubled.values():
if i != 0:
return []
return(ans)