<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>

# # Time: O(nlogn)
# class Solution:
#     def findOriginalArray(self, changed: List[int]) -> List[int]:
#         n = len(changed)

#         if n % 2 != 0: return []

#         changed.sort()

#         freq = Counter(changed)

#         ans = []

#         for c in changed:
#             if freq[c]:
#                 freq[c] -= 1
#                 k = c * 2
#                 if freq[k]:
#                     freq[k] -= 1
#                     ans.append(c)
#                 else:
#                     return []
        
#         return ans

# Time: O(n + k) k is the largest number
# Space: O(k)
class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        n = len(changed)
        if n % 2 != 0:
            return []
        
        max_num = max(changed)
        freq = [0] * (max_num * 2 + 1)  # Frequency array up to max_num * 2
        
        # Build frequency array
        for num in changed:
            freq[num] += 1
        
        ans = []
        
        # Handle zeros separately
        if freq[0] % 2 != 0:
            return []
        ans.extend([0] * (freq[0] // 2))
        freq[0] = 0
        
        # Process numbers from smallest to largest
        for num in range(1, max_num + 1):
            if freq[num] > 0:
                double_num = num * 2
                if double_num >= len(freq) or freq[double_num] < freq[num]:
                    return []
                freq[double_num] -= freq[num]
                ans.extend([num] * freq[num])
                freq[num] = 0
        
        return ans
317