Problem statement

https://leetcode.com/problems/find-original-array-from-doubled-array/

Solution

This problem is very similar to problem 0954. Array of Doubled Pairs. The idea is that for the smallest number there is unique way to find its pair. So, we sort numbers and then start from the smallest numbers, each time looking for pairs. If we can not find pair, return []. The only difference, which costs me 5 minutes fine was that we need to deal with 0 as well.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def findOriginalArray(self, arr):
        cnt, ans = Counter(arr), []
        for num in sorted(arr, key = lambda x: abs(x)):
            if cnt[num] == 0: continue
            if cnt[2*num] == 0: return []
            ans += [num]
            if num == 0 and cnt[num] <= 1: return []
            cnt[num] -= 1
            cnt[2*num] -= 1
        
        return ans

If you have any questions, feel free to ask. If you like solution and explanations, please Upvote!