Scale Engineer

Minimum Number Game

Easy
#2654Time: 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`.
Algorithms
Sorting
Data structures
ArrayHeap (Priority Queue)

Prompt

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 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 <= 100
  • 1 <= nums[i] <= 100
  • nums.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 nums to a more flexible data structure like an ArrayList to handle dynamic removals.
  • Create an empty ArrayList to store the result, arr.
  • Loop as long as the list of numbers is not empty:
    1. Find the minimum element in the current list (Alice's pick).
    2. Remove this element from the list.
    3. Find the new minimum element in the list (Bob's pick).
    4. Remove this element from the list.
    5. Append Bob's pick to arr.
    6. Append Alice's pick to arr.
  • Convert the final arr list 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.

Solutions

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;  }}

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

← Previous

Previous problem

Next →

Next problem