Minimum Number Game - Solution & Explanation
Problem Statement
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
numsbecomes 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 <= 1001 <= nums[i] <= 100nums.length % 2 == 0
Approach Overview
Problem Overview: You are given an integer array nums. In each step of the game, remove the two smallest numbers. Alice takes the smallest and Bob takes the second smallest, but Bob's number is placed in the result first followed by Alice's. Repeat until the array is empty and return the constructed sequence.
Approach 1: Simulate the Game Using Sorting (O(n log n) time, O(1) extra space)
The key observation: every round always selects the two smallest remaining numbers. If you sort the array first, those pairs naturally appear next to each other. After sorting in ascending order, iterate through the array with a step of two and swap each pair (nums[i], nums[i+1]). Append the second element first and the first element second to simulate Bob placing his number before Alice's. Sorting guarantees the pair represents the two smallest available values at that step. This approach is simple, reliable, and commonly expected in interviews when working with arrays and sorting.
Approach 2: Two Pointers Without Sorting (O(nĀ²) time, O(1) space)
If sorting is not allowed, simulate the process directly. In each round, scan the remaining portion of the array to find the smallest and second smallest elements. Two indices track these candidates while iterating through the array. Once identified, append the second smallest value first (Bob) and then the smallest (Alice). Mark or move those elements so they are not used again. Because each round requires scanning the remaining numbers to locate two minimums, the total work grows quadratically. This approach demonstrates the raw simulation logic but is less efficient than sorting.
A variation sometimes discussed uses a heap (priority queue). Push all elements into a min-heap and pop twice each round. The first pop is Alice's number and the second is Bob's, but you append them in reverse order. That version runs in O(n log n) time similar to sorting but with additional heap overhead.
Recommended for interviews: The sorting-based simulation is the expected solution. It reduces the game mechanics to a simple observation: the smallest values will always be paired together. Showing the naive scanning approach first demonstrates understanding of the game rules, but the sorted pairing solution proves you can simplify the process and achieve O(n log n) efficiency.
Approach 1: Approach 1: Simulate the Game Using Sorting
This approach involves sorting the nums array first. By doing this, Alice always picks the current first (or minimum) element in the sorted array. Bob then picks the next minimum element, which is the next in order in the sorted version.
This simulation essentially involves maintaining pointers or indices to add elements accordingly to arr.
First, we use the qsort function to sort the input array. We then iterate through the sorted array two elements at a time, adding the larger element first (Bob's action) then the smaller element (Alice's action) to the arr.
Complexity
Time complexity: O(n log n) due to sorting.
Space complexity: O(1) since no additional space is used beyond arr.
Approach 2: Approach 2: Two Pointers Without Sorting
This approach involves using two pointers to simulate the game without explicitly sorting the array. By repeatedly finding and removing the minimum two elements, it mimics the sorting behavior.
This code iterates over the nums repeatedly to find the minimum two available numbers. These numbers are added to arr, while marking the respective array slots to a high value to prevent reselection.
Complexity
Time complexity: O(n^2) due to repeatedly searching the list.
Space complexity: O(1) as no additional storage is required beyond input size.
Approach 3: Simulation + Priority Queue (Min Heap)
We can put the elements of the array nums into a min heap one by one. Each time, we take out two elements a and b from the min heap, and then sequentially put b and a into the answer array until the min heap is empty.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums.
Approach 4: Sorting + Swapping
We can sort the array nums, and then iterate through the array, swapping adjacent elements each time until the iteration is complete, and return the swapped array.
The time complexity is O(n log n), and the space complexity is O(log n). Here, n is the length of the array nums.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Simulate the Game Using Sorting | Time complexity: O(n log n) due to sorting. |
| Approach 2: Two Pointers Without Sorting | Time complexity: O(n^2) due to repeatedly searching the list. |
| Simulation + Priority Queue (Min Heap) | ā |
| Sorting + Swapping | ā |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulate Using Sorting | O(n log n) | O(1) extra | Best general solution. Simple implementation after sorting the array. |
| Two Pointers Without Sorting | O(nĀ²) | O(1) | Useful for understanding the raw simulation when sorting or extra structures are avoided. |
Video Solution
Leetcode | 2974. Minimum Number Game | Easy | Java Solution ā¢ Developer Docs ā¢ 1,579 views views
Watch 9 more video solutions āFrequently Asked Questions
Is Minimum Number Game easy or hard?
How to solve Minimum Number Game in O(n)?
Minimum Number Game Python or Java solution?
What is the best approach for Minimum Number Game?
What data structure is used in Minimum Number Game?
What is the time complexity of Minimum Number Game?
Is Minimum Number Game asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Minimum Number Game with our built-in code editor and test cases.
Practice on FleetCode