Minimum Number Game

Difficulty: Easy | Acceptance: 85.50% | Paid: No Topics: Array, Sorting, Heap (Priority Queue), Simulation

You are given a 0-indexed integer array nums of even length.

There is a game being played with this array. In each round of the game, the following occurs:

1. Alice removes the smallest element from nums, adds it to arr, and removes it from nums.
2. Bob removes the smallest element from nums, adds it to arr, and removes it from nums.
3. Alice adds the element Bob removed to arr.
4. Bob adds the element Alice removed to arr.

The game continues until nums is empty.

Return the array arr.

• Examples
• Constraints
• Approach 1: Sorting
• Approach 2: Min-Heap Simulation

Examples

Example 1

Input: nums = [5,4,2,3]
Output: [3,2,5,4]
Explanation:
In round one, first Alice removes 2 and adds it to arr. Then Bob removes 3 and adds it to arr. Finally, Alice adds 3 and Bob adds 2 to arr. arr = [3,2].
In round two, first Alice removes 4 and adds it to arr. Then Bob removes 5 and adds it to arr. Finally, Alice adds 5 and Bob adds 4 to arr. arr = [3,2,5,4].

Example 2

Input: nums = [2,5]
Output: [5,2]
Explanation:
In round one, first Alice removes 2 and adds it to arr. Then Bob removes 5 and adds it to arr. Finally, Alice adds 5 and Bob adds 2 to arr. arr = [5,2].

Constraints

2 <= nums.length <= 50
1 <= nums[i] <= 100
nums.length is even.

Approach 1: Sorting

Intuition The game mechanics effectively sort the array and then swap every adjacent pair of elements. Alice picks the smallest, Bob picks the next smallest, but they append them in reverse order (Bob’s then Alice’s).

Steps

• Sort the array nums in ascending order.
• Iterate through the sorted array with a step of 2.
• Swap the element at the current index i with the element at index i + 1.
• Return the modified array.

class Solution:
    def numberGame(self, nums: list[int]) -> list[int]:
        nums.sort()
        for i in range(0, len(nums), 2):
            nums[i], nums[i+1] = nums[i+1], nums[i]
        return nums

Complexity

• Time: O(n log n) due to the sorting step.
• Space: O(1) or O(n) depending on the sorting algorithm’s implementation.
• Notes: This is the most efficient approach as sorting is the bottleneck.

Approach 2: Min-Heap Simulation

Intuition We can simulate the game exactly as described using a Min-Heap (Priority Queue). This allows us to repeatedly extract the smallest available number efficiently.

Steps

• Insert all elements from nums into a Min-Heap.
• Initialize an empty result array arr.
• While the heap is not empty:
  • Pop the smallest element (Alice’s pick).
  • Pop the next smallest element (Bob’s pick).
  • Append Bob’s element, then Alice’s element to arr.
• Return arr.

import heapq
from typing import List

class Solution:
    def numberGame(self, nums: List[int]) -> List[int]:
        heapq.heapify(nums)
        arr = []
        while nums:
            alice = heapq.heappop(nums)
            bob = heapq.heappop(nums)
            arr.append(bob)
            arr.append(alice)
        return arr

Complexity

• Time: O(n log n) for heap operations.
• Space: O(n) to store the heap.
• Notes: This approach directly simulates the game logic but requires extra space for the heap data structure.