# Minimum Number Game
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-number-game)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-game
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue)
---
## Problem
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 and Bob will do one move. The rules of the game are as follows:

* Every round, first 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`.

**Example 1:**

**Input:** nums = [5,4,2,3]
**Output:** [3,2,5,4]
**Explanation:** In round one, first Alice removes 2 and then Bob removes 3. Then in arr firstly Bob appends 3 and then Alice appends 2. So arr = [3,2].
At the begining of round two, nums = [5,4]. Now, first Alice removes 4 and then Bob removes 5. Then both append in arr which becomes [3,2,5,4].

**Example 2:**

**Input:** nums = [2,5]
**Output:** [5,2]
**Explanation:** In round one, first Alice removes 2 and then Bob removes 5. Then in arr firstly Bob appends and then Alice appends. So arr = [5,2].

**Constraints:**

* `2 <= nums.length <= 100`
* `1 <= nums[i] <= 100`
* `nums.length % 2 == 0`

# Approaches
## Brute-Force Simulation
This approach directly simulates the game round by round as described in the problem. In each round, it finds and removes the two smallest elements from the current list of numbers and appends them to the result array in the specified order (Bob's pick, then Alice's pick).
**Time:** O(N^2). Let N be the number of elements in `nums`. The main loop runs N/2 times. Inside the loop, finding the minimum element (`Collections.min`) and removing it (`numList.remove`) both take O(k) time, where k is the current size of the list. This leads to a total time complexity of O(N^2). · **Space:** O(N). We use an `ArrayList` to store a copy of the numbers and another `ArrayList` for the result, both of which require space proportional to the input size `N`.
**Pros:** Easy to understand as it's a direct translation of the problem statement into code.
**Cons:** Highly inefficient due to repeated linear scans (`O(N)`) to find the minimum element inside a loop.; The complexity becomes `O(N^2)`, which is slow for larger arrays.
### Explanation
We start by converting the input array `nums` into a data structure that allows for easy removal of elements, such as an `ArrayList`. The simulation then proceeds in a loop that continues as long as there are numbers left. Inside the loop, for each round, we first find and remove the minimum element for Alice, then find and remove the new minimum for Bob. This requires scanning the list twice per round. Finally, we append the elements removed by Bob and Alice to the result array in that order. This process is repeated until the initial list of numbers is empty.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int[] numberGame(int[] nums) {
        List<Integer> numList = new ArrayList<>();
        for (int num : nums) {
            numList.add(num);
        }

        List<Integer> arr = new ArrayList<>();
        while (!numList.isEmpty()) {
            // Alice's move: find and remove minimum
            int aliceRemoved = Collections.min(numList);
            numList.remove(Integer.valueOf(aliceRemoved));

            // Bob's move: find and remove new minimum
            int bobRemoved = Collections.min(numList);
            numList.remove(Integer.valueOf(bobRemoved));

            // Appending to arr as per rules
            arr.add(bobRemoved);
            arr.add(aliceRemoved);
        }

        // Convert result list to array
        int[] result = new int[nums.length];
        for (int i = 0; i < arr.size(); i++) {
            result[i] = arr.get(i);
        }
        return result;
    }
}
```
### Algorithm
- Convert the input array `nums` to a more flexible data structure like an `ArrayList` to handle dynamic removals.
- Create an empty `ArrayList` to store the result, `arr`.
- Loop as long as the list of numbers is not empty:
  1. Find the minimum element in the current list (Alice's pick).
  2. Remove this element from the list.
  3. Find the new minimum element in the list (Bob's pick).
  4. Remove this element from the list.
  5. Append Bob's pick to `arr`.
  6. Append Alice's pick to `arr`.
- Convert the final `arr` list back to an array and return it.

## Optimized Simulation with a Min-Heap
This approach improves upon the brute-force simulation by using a more efficient data structure to find the minimum element. A min-heap allows us to retrieve the minimum element in logarithmic time, which is much faster than the linear time search of the previous approach.
**Time:** O(N log N). Building the heap by adding `N` elements one by one takes `O(N log N)`. Subsequently, we perform `N` poll operations in total, each taking `O(log k)` time where `k` is the current size of the heap. The total time is dominated by these operations. · **Space:** O(N). We need a priority queue to store all `N` elements, and a result array of size `N`.
**Pros:** Significantly more efficient than the brute-force approach with a time complexity of O(N log N).; Still conceptually follows the game's flow of picking minimums.
**Cons:** Requires extra space for the heap, in addition to the result array.
### Explanation
Instead of repeatedly scanning a list, we can leverage a min-heap. First, we build the min-heap from all the numbers in the input array. This operation takes `O(N log N)` time. The top element of the min-heap is always the smallest number. The game simulation then becomes a series of extractions from the heap. In each step, we extract the minimum for Alice, then extract the new minimum for Bob. Each extraction (`poll`) takes `O(log k)` time, where `k` is the heap size. We append these two elements to our result array in the specified order (Bob's, then Alice's) and repeat until the heap is empty.

```java
import java.util.PriorityQueue;

class Solution {
    public int[] numberGame(int[] nums) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.add(num);
        }

        int[] arr = new int[nums.length];
        int i = 0;
        while (!minHeap.isEmpty()) {
            int aliceRemoved = minHeap.poll();
            int bobRemoved = minHeap.poll();
            
            arr[i] = bobRemoved;
            arr[i+1] = aliceRemoved;
            i += 2;
        }
        
        return arr;
    }
}
```
### Algorithm
- Create a min-heap (a `PriorityQueue` in Java) and insert all elements from the `nums` array into it.
- Create a result array `arr` of the same size as `nums`.
- While the heap is not empty:
  1. Extract the minimum element from the heap (`poll()`). This is Alice's pick (`alice_removed`).
  2. Extract the new minimum element from the heap. This is Bob's pick (`bob_removed`).
  3. Place `bob_removed` and then `alice_removed` into the result array `arr`.
- Return the `arr`.

## Sorting-based Approach
This is the most efficient and straightforward approach. By observing the game's mechanics, we can deduce that the process is equivalent to sorting the numbers and then swapping every adjacent pair. The final result `arr` is simply a sequence of these pairs, but with the larger number of each pair appearing before the smaller one.
**Time:** O(N log N). The runtime is dominated by the initial sorting step. The subsequent loop to swap pairs runs in linear time, O(N). · **Space:** O(log N) to O(N). The space complexity is determined by the sorting algorithm used. In Java, `Arrays.sort()` for primitive types uses a dual-pivot quicksort, which requires `O(log N)` space on average for the recursion stack. The swapping is done in-place, requiring no additional space.
**Pros:** Elegant, concise, and highly efficient.; Often faster in practice than the heap-based approach due to better cache performance and lower constant factors.; Can be done in-place, making it very space-efficient.
**Cons:** The connection to the original game simulation is less direct and requires an initial insight into the pattern.
### Explanation
The key insight is that the game effectively sorts the numbers and then reorders them. In any round, Alice picks the smallest available number (`min1`) and Bob picks the second smallest (`min2`). They are then placed in the result array as `(min2, min1)`. If we sort the entire `nums` array initially, the elements `nums[0]` and `nums[1]` would be the first pair picked, `nums[2]` and `nums[3]` the second, and so on. The final arrangement can be achieved by simply sorting the array and then swapping each adjacent pair of elements.

```java
import java.util.Arrays;

class Solution {
    public int[] numberGame(int[] nums) {
        // Sort the array in ascending order
        Arrays.sort(nums);
        
        // Iterate through the array and swap adjacent elements
        for (int i = 0; i < nums.length; i += 2) {
            // Swap nums[i] and nums[i+1]
            int temp = nums[i];
            nums[i] = nums[i+1];
            nums[i+1] = temp;
        }
        
        return nums;
    }
}
```
### Algorithm
- Sort the input array `nums` in non-decreasing order.
- Iterate through the sorted array with a step of 2 (i.e., `i = 0, 2, 4, ...`).
- For each pair of elements at indices `i` and `i+1`, swap them.
- Return the modified `nums` array.

# Solutions
### Java

```java
class Solution {
public
  int[] numberGame(int[] nums) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for (int x : nums) {
      pq.offer(x);
    }
    int[] ans = new int[nums.length];
    int i = 0;
    while (!pq.isEmpty()) {
      int a = pq.poll();
      ans[i++] = pq.poll();
      ans[i++] = a;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> numberGame(vector<int> &nums) {
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int x : nums) {
      pq.push(x);
    }
    vector<int> ans;
    while (pq.size()) {
      int a = pq.top();
      pq.pop();
      int b = pq.top();
      pq.pop();
      ans.push_back(b);
      ans.push_back(a);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numberGame(self, nums: List[int]) -> List[int]: heapify(nums) ans = [] while nums: a, b = heappop(nums), heappop(nums) ans . append(b) ans . append(a) return ans

```