Problem Description
Given an even-length integer array nums, two players (Alice and Bob) play a game. In each round, Alice removes the minimum element followed by Bob removing the new minimum element from nums. Then, Bob appends his removed element to an initially empty array arr, and Alice appends hers. The game continues until nums is empty. Return the resulting arr.
Key Insights
- Since the game always picks the two smallest elements per round, sorting the array provides a natural order.
- After sorting, each pair in order represents Alice’s (smallest) and Bob’s (second smallest) removals.
- The order of appending is reversed compared to the removal order: Bob’s removed number is appended before Alice’s.
Space and Time Complexity
Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) for storing the output array.
Solution
The solution leverages sorting. After sorting the array in ascending order, the smallest and second smallest numbers are grouped as pairs. In each pair, the first element corresponds to Alice’s removal and the second corresponds to Bob’s. Since Bob appends his number first, followed by Alice, the pair in the result is arranged as (second element, first element). This logic is repeated for all pairs in the sorted array, ensuring the correct game order.