2007.md

2007. Find Original Array From Doubled Array

Solution 1 (time O(nlog(n)), space O(n))

class Solution(object):
    def findOriginalArray(self, changed):
        """
        :type changed: List[int]
        :rtype: List[int]
        """
        n = len(changed)
        changed.sort()
        ans = []
        info = collections.defaultdict(int)
        for num in changed:
            if info[num] == 0:
                ans.append(num)
                info[num * 2] += 1
            else:
                info[num] -= 1
        for k, v in info.items():
            if v != 0:
                return []
        return ans