<p>An integer array <code>original</code> is transformed into a <strong>doubled</strong> array <code>changed</code> by appending <strong>twice the value</strong> of every element in <code>original</code>, and then randomly <strong>shuffling</strong> the resulting array.</p>

<p>Given an array <code>changed</code>, return <code>original</code><em> if </em><code>changed</code><em> is a <strong>doubled</strong> array. If </em><code>changed</code><em> is not a <strong>doubled</strong> array, return an empty array. The elements in</em> <code>original</code> <em>may be returned in <strong>any</strong> order</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> changed = [1,3,4,2,6,8]
<strong>Output:</strong> [1,3,4]
<strong>Explanation:</strong> 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].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> changed = [6,3,0,1]
<strong>Output:</strong> []
<strong>Explanation:</strong> changed is not a doubled array.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> changed = [1]
<strong>Output:</strong> []
<strong>Explanation:</strong> changed is not a doubled array.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= changed.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= changed[i] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        """
        https://www.youtube.com/watch?v=z40B-Mr9_qk

        We can't know for sure if a value is part of the original value or the doubled value
        But we can say the smallest element in changed is for sure part of the original array
        - because the smallest element can not be a doubled value
        We must sort the array O(nlogn)

        We can loop through the sorted array, remove the value and the doubled value from changed
        - NOTE: if you are thinking of trying to iterate over a mutating OrderedDict, you will get runtime error
        - NOTE: if you are thinking of trying while loop with min-heap, it would just cause chaos, don't
        - NOTE: if you are thinking of trying to use a separate hashset for removal...you are on the right track, but
            also not quite there, because you forgot about duplicates...read on...

        There might be duplicates
        changed = [1,2,2,4], original = [1,2]

        We need to keep track of the freq of elements in a hashtable
        Removing the values will mean decrementing the count by 1

        If the value and doubled value has a count above 0, we append value to result
        - NOTE: why do we not return empty list right away when we see the value and doubled value has a count below 0?
            Because we don't know if the current value is part of the original value or the doubled value

        If final result length is half of changed, then we have the solution!
        """
        if len(changed) % 2 != 0:
            return []

        # create the counter
        from collections import defaultdict
        counter = defaultdict(int)
        for num in changed:
            counter[num] += 1
        
        # sort the array
        changed.sort()

        # loop through the sorted array and populate the result
        res = []
        for num in changed:
            # special case
            if num == 0 and counter[num] > 1:
                counter[num] -= 2
                res.append(num)
            elif num != 0 and counter[num] > 0 and counter[num * 2] > 0:
                counter[num] -= 1
                counter[num * 2] -= 1
                res.append(num)
        
        return res if len(res) == len(changed) // 2 else []

1103