LeetCode 2974 - Minimum Number Game

Difficulty: 🟢 Easy
Topics: Array, Sorting, Heap (Priority Queue), Simulation

Solution

Problem Understanding

The problem gives us an integer array nums with an even number of elements. We repeatedly simulate a game between Alice and Bob until the array becomes empty.

In each round, the following sequence happens:

Alice removes the smallest remaining number.
Bob removes the next smallest remaining number.
Bob appends his removed number to the result array arr.
Alice appends her removed number to arr.

The important detail is that although Alice removes first, Bob inserts first into the final array.

The goal is to return the final array arr after all rounds are completed.

Another way to think about the problem is this:

Sort the numbers in ascending order.
Process them in pairs.
For every adjacent pair (a, b) where a < b, append them as (b, a) to the answer.

For example:

nums = [2,3,4,5]

Alice removes 2, Bob removes 3, and the result receives [3,2].

Then Alice removes 4, Bob removes 5, and the result receives [5,4].

Final answer:

[3,2,5,4]

The constraints are very small:

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

These constraints tell us several important things:

Performance is not a major concern because the input size is tiny.
Even a less efficient simulation would still pass comfortably.
The even length guarantee means we will always be able to remove numbers in pairs.
Values are small, so sorting is straightforward.

An important observation is that the game behavior is completely determined by the sorted order of the numbers. We never need to repeatedly search for the minimum if we sort once at the beginning.

Some edge cases worth considering are:

The smallest valid input size, such as [2,5]
Arrays with duplicate values
Arrays already sorted
Arrays sorted in descending order
Arrays where all values are identical

The problem guarantees valid input, so we never need to handle odd-length arrays or empty arrays.

Approaches

Brute Force Approach

A direct simulation would repeatedly perform exactly what the problem statement describes.

In every round:

Find the minimum element in nums and remove it.
Find the new minimum element and remove it.
Append the second removed value first.
Append the first removed value second.

This approach is correct because it follows the rules literally. However, removing minimum elements from a normal array is inefficient because each search for the minimum costs linear time, and removing an element also requires shifting elements.

If there are n elements, then we perform roughly n/2 rounds, and each round may require linear work to locate and remove elements. This leads to quadratic complexity.

Optimal Approach

The key observation is that the game always removes numbers in ascending order.

Suppose the sorted array is:

[a1, a2, a3, a4, ...]

Then:

Alice removes a1
Bob removes a2
Output becomes [a2, a1]

Alice removes a3
Bob removes a4
Output becomes [a2, a1, a4, a3]

So after sorting, we only need to swap every adjacent pair.

This reduces the problem to:

Sort the array.
Iterate through it two elements at a time.
Append the pair in reversed order.

This is simpler and more efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly searches and removes minimum elements
Optimal	O(n log n)	O(1) or O(n)	Sort once, then swap adjacent pairs

Algorithm Walkthrough

Sort the array in ascending order.

Sorting guarantees that the numbers appear in the exact order they would be removed during the game. After sorting, every consecutive pair represents one round of the game. 2. Create an empty result array.

This array will store the final sequence produced by the game. 3. Iterate through the sorted array in steps of two.

At each iteration:

nums[i] represents Alice's removed value
nums[i + 1] represents Bob's removed value

Append Bob's number first.

Since Bob inserts into arr before Alice, we append nums[i + 1] first. 5. Append Alice's number second.

Then append nums[i]. 6. Continue until all pairs are processed.

Because the array length is guaranteed to be even, every iteration safely processes exactly one pair. 7. Return the result array.

Why it works

After sorting, the numbers appear in the exact order they are removed from the game. Every round always consumes the two smallest remaining numbers. Therefore, each adjacent pair in the sorted array corresponds to one round. Reversing each pair reproduces the exact insertion order into arr, which guarantees the algorithm matches the game simulation perfectly.

Python Solution

from typing import List

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

The implementation starts by sorting nums so the values appear in the order they would be removed during the game.

A new list called result stores the final answer.

The loop advances by two positions at a time because every game round consumes exactly two numbers. Inside the loop:

nums[i] is Alice's number
nums[i + 1] is Bob's number

Since Bob appends first, we insert nums[i + 1] before nums[i].

Finally, the completed result array is returned.

Go Solution

package main

import "sort"

func numberGame(nums []int) []int {
	sort.Ints(nums)

	result := make([]int, 0, len(nums))

	for i := 0; i < len(nums); i += 2 {
		result = append(result, nums[i+1])
		result = append(result, nums[i])
	}

	return result
}

The Go implementation follows the same logic as the Python version.

sort.Ints(nums) sorts the slice in ascending order. A result slice is created with capacity equal to the input size to avoid unnecessary reallocations during appends.

The loop processes elements in pairs and appends them in reversed order.

Since all values are small integers and the array size is tiny, integer overflow is not a concern. Go slices naturally handle dynamic resizing, though preallocating capacity improves efficiency slightly.

Worked Examples

Example 1

nums = [5,4,2,3]

Step 1: Sort the array

[2,3,4,5]

Step 2: Process pairs

Iteration	Pair	Bob Appends	Alice Appends	Result
1	(2,3)	3	2	[3,2]
2	(4,5)	5	4	[3,2,5,4]

Final output:

[3,2,5,4]

Example 2

nums = [2,5]

Step 1: Sort the array

[2,5]

Step 2: Process pair

Iteration	Pair	Bob Appends	Alice Appends	Result
1	(2,5)	5	2	[5,2]

Final output:

[5,2]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(n)	The result array stores all elements

The sorting operation requires O(n log n) time. After sorting, the algorithm performs a single linear pass through the array, which costs O(n) time.

The output array contains all elements from the input, so the auxiliary space usage is O(n). Some sorting implementations may also use additional internal memory, but the dominant explicit extra space is the result array.

Test Cases

from typing import List

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

solution = Solution()

assert solution.numberGame([5,4,2,3]) == [3,2,5,4]  # Example 1
assert solution.numberGame([2,5]) == [5,2]  # Example 2

assert solution.numberGame([1,2]) == [2,1]  # Smallest valid input
assert solution.numberGame([1,2,3,4]) == [2,1,4,3]  # Already sorted input
assert solution.numberGame([4,3,2,1]) == [2,1,4,3]  # Reverse sorted input

assert solution.numberGame([1,1,2,2]) == [1,1,2,2]  # Duplicate values
assert solution.numberGame([7,7,7,7]) == [7,7,7,7]  # All identical values

assert solution.numberGame([10,1,8,2,6,4]) == [2,1,6,4,10,8]  # Mixed ordering
assert solution.numberGame([100,99,98,97]) == [98,97,100,99]  # Large values within constraints

Test	Why
`[5,4,2,3]`	Validates the main example
`[2,5]`	Tests smallest possible array
`[1,2]`	Verifies single-round behavior
`[1,2,3,4]`	Confirms already sorted input works
`[4,3,2,1]`	Confirms sorting is necessary
`[1,1,2,2]`	Tests duplicate handling
`[7,7,7,7]`	Tests identical values
`[10,1,8,2,6,4]`	Tests arbitrary ordering
`[100,99,98,97]`	Tests upper value range

Edge Cases

Minimum Input Size

The smallest valid input contains exactly two numbers. This case is important because the algorithm processes elements in pairs. Off by one errors often appear when loops increment by two.

For example:

[2,5]

After sorting, the algorithm swaps the only pair and returns [5,2]. The implementation handles this naturally because the loop executes exactly once.

Duplicate Values

Arrays may contain repeated numbers, which can sometimes break algorithms that incorrectly assume uniqueness.

For example:

[1,1,2,2]

Sorting produces:

[1,1,2,2]

Each adjacent pair is reversed, but identical numbers remain unchanged. The implementation correctly preserves duplicates because it relies only on ordering, not uniqueness.

Reverse Sorted Input

An input may initially appear in descending order:

[5,4,3,2]

A naive implementation that skips sorting would fail here because the game always removes the smallest available numbers first.

The sorting step ensures the algorithm always reconstructs the correct removal order before processing pairs.

All Elements Identical

When every number is the same:

[7,7,7,7]

every pair reversal produces the same values. This edge case verifies that the implementation does not depend on strict inequalities between numbers.

The algorithm still works correctly because sorting and swapping adjacent equal values leaves the array unchanged.