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 arrayarr.

Examples

Example 1

1
2
3
4

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

1
2
3

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

Solution

Method 1 – Sorting and Simulation

Intuition

Since Alice and Bob always pick the minimum elements, sorting the array allows us to simulate the game efficiently. Bob always appends his pick first, then Alice, so we alternate appending from the sorted array.

Approach

  1. Sort nums in ascending order.
  2. For each round, Bob appends the smallest remaining element, then Alice appends the next smallest.
  3. Continue until all elements are appended.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    vector<int> numberGame(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> ans;
        for (int i = 0; i < nums.size(); i += 2) {
            ans.push_back(nums[i+1]);
            ans.push_back(nums[i]);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8

func numberGame(nums []int) []int {
    sort.Ints(nums)
    ans := make([]int, 0, len(nums))
    for i := 0; i < len(nums); i += 2 {
        ans = append(ans, nums[i+1], nums[i])
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int[] numberGame(int[] nums) {
        Arrays.sort(nums);
        int[] ans = new int[nums.length];
        int idx = 0;
        for (int i = 0; i < nums.length; i += 2) {
            ans[idx++] = nums[i+1];
            ans[idx++] = nums[i];
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun numberGame(nums: IntArray): IntArray {
        nums.sort()
        val ans = IntArray(nums.size)
        var idx = 0
        for (i in nums.indices step 2) {
            ans[idx++] = nums[i+1]
            ans[idx++] = nums[i]
        }
        return ans
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def numberGame(self, nums: list[int]) -> list[int]:
        nums.sort()
        ans: list[int] = []
        for i in range(0, len(nums), 2):
            ans.append(nums[i+1])
            ans.append(nums[i])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn number_game(mut nums: Vec<i32>) -> Vec<i32> {
        nums.sort();
        let mut ans = Vec::with_capacity(nums.len());
        let n = nums.len();
        let mut i = 0;
        while i < n {
            ans.push(nums[i+1]);
            ans.push(nums[i]);
            i += 2;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    numberGame(nums: number[]): number[] {
        nums.sort((a, b) => a - b);
        const ans: number[] = [];
        for (let i = 0; i < nums.length; i += 2) {
            ans.push(nums[i+1], nums[i]);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), for sorting the array.
  • 🧺 Space complexity: O(n), for the answer array.