Minimum Number Game
EasyPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the game round by round as described in the problem. In each round, it finds and removes the two smallest elements from the current list of numbers and appends them to the result array in the specified order (Bob's pick, then Alice's pick).
Algorithm
- Convert the input array
numsto a more flexible data structure like anArrayListto handle dynamic removals. - Create an empty
ArrayListto store the result,arr. - Loop as long as the list of numbers is not empty:
- Find the minimum element in the current list (Alice's pick).
- Remove this element from the list.
- Find the new minimum element in the list (Bob's pick).
- Remove this element from the list.
- Append Bob's pick to
arr. - Append Alice's pick to
arr.
- Convert the final
arrlist back to an array and return it.
Walkthrough
We start by converting the input array nums into a data structure that allows for easy removal of elements, such as an ArrayList. The simulation then proceeds in a loop that continues as long as there are numbers left. Inside the loop, for each round, we first find and remove the minimum element for Alice, then find and remove the new minimum for Bob. This requires scanning the list twice per round. Finally, we append the elements removed by Bob and Alice to the result array in that order. This process is repeated until the initial list of numbers is empty.
import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution { public int[] numberGame(int[] nums) { List<Integer> numList = new ArrayList<>(); for (int num : nums) { numList.add(num); } List<Integer> arr = new ArrayList<>(); while (!numList.isEmpty()) { // Alice's move: find and remove minimum int aliceRemoved = Collections.min(numList); numList.remove(Integer.valueOf(aliceRemoved)); // Bob's move: find and remove new minimum int bobRemoved = Collections.min(numList); numList.remove(Integer.valueOf(bobRemoved)); // Appending to arr as per rules arr.add(bobRemoved); arr.add(aliceRemoved); } // Convert result list to array int[] result = new int[nums.length]; for (int i = 0; i < arr.size(); i++) { result[i] = arr.get(i); } return result; }}Complexity
Time
O(N^2). Let N be the number of elements in `nums`. The main loop runs N/2 times. Inside the loop, finding the minimum element (`Collections.min`) and removing it (`numList.remove`) both take O(k) time, where k is the current size of the list. This leads to a total time complexity of O(N^2).
Space
O(N). We use an `ArrayList` to store a copy of the numbers and another `ArrayList` for the result, both of which require space proportional to the input size `N`.
Trade-offs
Pros
Easy to understand as it's a direct translation of the problem statement into code.
Cons
Highly inefficient due to repeated linear scans (
O(N)) to find the minimum element inside a loop.The complexity becomes
O(N^2), which is slow for larger arrays.
This approach improves upon the brute-force simulation by using a more efficient data structure to find the minimum element. A min-heap allows us to retrieve the minimum element in logarithmic time, which is much faster than the linear time search of the previous approach.
Algorithm
- Create a min-heap (a
PriorityQueuein Java) and insert all elements from thenumsarray into it. - Create a result array
arrof the same size asnums. - While the heap is not empty:
- Extract the minimum element from the heap (
poll()). This is Alice's pick (alice_removed). - Extract the new minimum element from the heap. This is Bob's pick (
bob_removed). - Place
bob_removedand thenalice_removedinto the result arrayarr.
- Extract the minimum element from the heap (
- Return the
arr.
Walkthrough
Instead of repeatedly scanning a list, we can leverage a min-heap. First, we build the min-heap from all the numbers in the input array. This operation takes O(N log N) time. The top element of the min-heap is always the smallest number. The game simulation then becomes a series of extractions from the heap. In each step, we extract the minimum for Alice, then extract the new minimum for Bob. Each extraction (poll) takes O(log k) time, where k is the heap size. We append these two elements to our result array in the specified order (Bob's, then Alice's) and repeat until the heap is empty.
import java.util.PriorityQueue; class Solution { public int[] numberGame(int[] nums) { PriorityQueue<Integer> minHeap = new PriorityQueue<>(); for (int num : nums) { minHeap.add(num); } int[] arr = new int[nums.length]; int i = 0; while (!minHeap.isEmpty()) { int aliceRemoved = minHeap.poll(); int bobRemoved = minHeap.poll(); arr[i] = bobRemoved; arr[i+1] = aliceRemoved; i += 2; } return arr; }}Complexity
Time
O(N log N). Building the heap by adding `N` elements one by one takes `O(N log N)`. Subsequently, we perform `N` poll operations in total, each taking `O(log k)` time where `k` is the current size of the heap. The total time is dominated by these operations.
Space
O(N). We need a priority queue to store all `N` elements, and a result array of size `N`.
Trade-offs
Pros
Significantly more efficient than the brute-force approach with a time complexity of O(N log N).
Still conceptually follows the game's flow of picking minimums.
Cons
Requires extra space for the heap, in addition to the result array.
This is the most efficient and straightforward approach. By observing the game's mechanics, we can deduce that the process is equivalent to sorting the numbers and then swapping every adjacent pair. The final result arr is simply a sequence of these pairs, but with the larger number of each pair appearing before the smaller one.
Algorithm
- Sort the input array
numsin non-decreasing order. - Iterate through the sorted array with a step of 2 (i.e.,
i = 0, 2, 4, ...). - For each pair of elements at indices
iandi+1, swap them. - Return the modified
numsarray.
Walkthrough
The key insight is that the game effectively sorts the numbers and then reorders them. In any round, Alice picks the smallest available number (min1) and Bob picks the second smallest (min2). They are then placed in the result array as (min2, min1). If we sort the entire nums array initially, the elements nums[0] and nums[1] would be the first pair picked, nums[2] and nums[3] the second, and so on. The final arrangement can be achieved by simply sorting the array and then swapping each adjacent pair of elements.
import java.util.Arrays; class Solution { public int[] numberGame(int[] nums) { // Sort the array in ascending order Arrays.sort(nums); // Iterate through the array and swap adjacent elements for (int i = 0; i < nums.length; i += 2) { // Swap nums[i] and nums[i+1] int temp = nums[i]; nums[i] = nums[i+1]; nums[i+1] = temp; } return nums; }}Complexity
Time
O(N log N). The runtime is dominated by the initial sorting step. The subsequent loop to swap pairs runs in linear time, O(N).
Space
O(log N) to O(N). The space complexity is determined by the sorting algorithm used. In Java, `Arrays.sort()` for primitive types uses a dual-pivot quicksort, which requires `O(log N)` space on average for the recursion stack. The swapping is done in-place, requiring no additional space.
Trade-offs
Pros
Elegant, concise, and highly efficient.
Often faster in practice than the heap-based approach due to better cache performance and lower constant factors.
Can be done in-place, making it very space-efficient.
Cons
The connection to the original game simulation is less direct and requires an initial insight into the pattern.
Solutions
Solution
class Solution {public int[] numberGame(int[] nums) { PriorityQueue<Integer> pq = new PriorityQueue<>(); for (int x : nums) { pq.offer(x); } int[] ans = new int[nums.length]; int i = 0; while (!pq.isEmpty()) { int a = pq.poll(); ans[i++] = pq.poll(); ans[i++] = a; } return ans; }}class Solution {public: vector<int> numberGame(vector<int> &nums) { priority_queue<int, vector<int>, greater<int>> pq; for (int x : nums) { pq.push(x); } vector<int> ans; while (pq.size()) { int a = pq.top(); pq.pop(); int b = pq.top(); pq.pop(); ans.push_back(b); ans.push_back(a); } return ans; }};class Solution: def numberGame(self, nums: List[int]) -> List[int]: heapify(nums) ans = [] while nums: a, b = heappop(nums), heappop(nums) ans . append(b) ans . append(a) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.