Minimum Number Game

Problem Description

You are given a 0-indexed integer array nums of even length and there is also an empty array arr. Alice and Bob decided to play a game where in every round Alice will remove the minimum element from nums, and then Bob does the same. Now, first Bob will append the removed element in the array arr, and then Alice does the same. The game continues until nums becomes empty. Return the resulting array arr.

Key Insights

• The game consists of alternating rounds where Alice and Bob take turns removing and appending minimum elements from/to their respective arrays.
• Since nums has an even length, each round will consist of both players making a move.
• The order of appending elements to arr matters and is determined by the sequence of removals.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the array initially. Space Complexity: O(n) - for the resulting array arr.

Solution

The solution involves the following steps:

1. Sort the input array nums to easily access the minimum elements.
2. Use a loop to simulate each round of the game, where Alice removes the first minimum and Bob removes the next minimum from the sorted array.
3. Append Bob's removed element to arr first, followed by Alice's.
4. Continue the process until all elements have been processed.

The primary data structure used here is a sorted array, which allows efficient retrieval of the minimum elements.

Code Solutions