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.
Summary (Approach)
Sort and greedy match counts:
- If
len(changed)is odd ⇒ return[]. - Count frequencies; iterate values ascending. For each
x, ensurefreq[2*x] >= freq[x](special casex==0: need even count). Appendxfreq[x]times tooriginal, decrementfreq[2*x]. If any check fails ⇒[].
Complexity: O(n log n) time (sorting), O(n) space.
The VOprep team has long accompanied candidates through various major company OAs and VOs, including NVIDIA , Google, Amazon, Citadel, SIG, providing real-time voice assistance, remote practice, and interview pacing reminders to help you stay smooth during critical moments. If you are preparing for Stripe or similar engineering-focused companies, you can check out our customized support plans—from coding interviews to system design, we offer full guidance to help you succeed.
