Minimum Number Game

easy array sorting simulation

Problem

You are given a 0-indexed integer array nums of even length. Alice and Bob play rounds: each round, Alice first removes the minimum element from nums, then Bob removes the minimum from what remains. Bob appends his removed number to the result array arr first, then Alice appends hers. Repeat until nums is empty, and return arr.

Inputnums = [5,4,2,3]

Output[3,2,5,4]

Round 1: Alice takes 2, Bob takes 3; Bob appends 3 then Alice 2. Round 2: Alice 4, Bob 5; append 5 then 4.

nums

def number_game(nums):
    nums.sort()
    arr = []
    for i in range(0, len(nums), 2):
        alice = nums[i]
        bob = nums[i + 1]
        arr.append(bob)
        arr.append(alice)
    return arr

function numberGame(nums) {
  nums.sort((a, b) => a - b);
  const arr = [];
  for (let i = 0; i < nums.length; i += 2) {
    const alice = nums[i];
    const bob = nums[i + 1];
    arr.push(bob);
    arr.push(alice);
  }
  return arr;
}

class Solution {
    public int[] numberGame(int[] nums) {
        Arrays.sort(nums);
        int[] arr = new int[nums.length];
        for (int i = 0; i < nums.length; i += 2) {
            arr[i] = nums[i + 1];
            arr[i + 1] = nums[i];
        }
        return arr;
    }
}

vector<int> numberGame(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<int> arr(nums.size());
    for (int i = 0; i < (int)nums.size(); i += 2) {
        arr[i] = nums[i + 1];
        arr[i + 1] = nums[i];
    }
    return arr;
}

Explanation

Each round both players take the smallest remaining number — Alice first, then Bob. Repeatedly pulling the minimum is exactly what happens if we sort the array once: the values come out in increasing order, two at a time.

After sorting, index 0 and 1 are the two smallest (Alice and Bob in round 1), indices 2 and 3 are the next round, and so on. Alice always grabs the even index i, Bob the odd index i+1, because Alice picks first and so gets the smaller of the pair.

The twist is the append order: Bob appends his number to the result before Alice. So within each pair we output nums[i+1] (Bob) followed by nums[i] (Alice), effectively swapping each adjacent pair of the sorted array.

This makes the whole solution a sort plus a single pass that walks in steps of two, swapping neighbors. No actual removal or priority queue is needed because sorting already orders every future minimum.

Example: [5,4,2,3] sorts to [2,3,4,5]. Pair (2,3) becomes 3,2; pair (4,5) becomes 5,4. Result: [3,2,5,4].

Time: O(n log n) Space: O(n)