2007. Find Original Array From Doubled Array

https://leetcode.com/problems/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.

class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        
        if len(changed) % 2:
            return []

        res = []
        # d = dict()
        # for num in changed:
        #     d[num] = d[num] + 1 if d.get(num) else 1
        d = Counter(changed)

        changed.sort()
        for num in changed:
            if d[num]: 
                d[num] -= 1
                if d.get(num*2):
                    res.append(num)
                    d[num*2] -= 1
            if len(res) == len(changed) // 2:
                return res
            

        return []

 

1. sort given list in ascending order.

2. find out doubled element in list iterating over the list

 

We must not exceed over O(n^2), so I used dictionary to count the number of elements. I excluded the element with zero numbers.