Minimum Number Game

Easy
628.

Minimum Number Game

Minimum Number Game is an easy coding problem on arrays, sorting and simulation, asked in TCS and Mindtree interviews.

Alice and Bob play with an array nums of even length and build a new array arr.

Each round: Alice removes the smallest remaining element, then Bob removes the smallest remaining element. Bob appends his element to arr first, then Alice appends hers.

Return arr once nums is empty.

Example 1

Input
nums = [5,4,2,3]
Output
[3,2,5,4]
Explanation
Round 1: Alice takes 2, Bob takes 3; Bob appends first, giving [3,2]. Round 2: Alice takes 4, Bob takes 5, giving [3,2,5,4].

Example 2

Input
nums = [2,5]
Output
[5,2]

Example 3

Input
nums = [1,1,2,2]
Output
[1,1,2,2]

Constraints

  • 2 <= nums.length <= 100
  • nums.length is even
  • 1 <= nums[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var numberGame = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Number Game — Solution in Python, Java & C++

Minimum Number Game solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays and sorting.

Minimum Number Game is an easy coding problem on arrays, sorting and simulation, asked in TCS and Mindtree interviews.

  • Difficulty: Easy
  • Topics: Arrays, Sorting, Simulation
  • Asked at: TCS, Mindtree
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Alice and Bob play with an array nums of even length and build a new array arr.

Each round: Alice removes the smallest remaining element, then Bob removes the smallest remaining element. Bob appends his element to arr first, then Alice appends hers.

Return arr once nums is empty.

Example 1

Input: nums = [5,4,2,3]
Output: [3,2,5,4]
Explanation: Round 1: Alice takes 2, Bob takes 3; Bob appends first, giving [3,2]. Round 2: Alice takes 4, Bob takes 5, giving [3,2,5,4].

Example 2

Input: nums = [2,5]
Output: [5,2]

Example 3

Input: nums = [1,1,2,2]
Output: [1,1,2,2]

Constraints

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

Hints for Minimum Number Game

  1. Hint 1

    Both players always take the smallest remaining element, so the removal order is simply sorted order.

  2. Hint 2

    Round t consumes the sorted elements at positions 2t and 2t + 1.

  3. Hint 3

    Bob appends first, so each pair is written to the output in swapped order.

How to solve Minimum Number Game

Neither player has a choice — both always take the minimum — so the whole game is 'sort the array, then swap each adjacent pair'.

Approach

  1. Sort nums ascending into s.
  2. Walk i in steps of two and append s[i+1] then s[i].
  3. Return the collected array.

Why it works

In round t the two smallest remaining values are s[2t] (Alice's) and s[2t+1] (Bob's). Bob appends before Alice, so the pair lands as s[2t+1], s[2t].

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Appending Alice's element first reverses every pair.
  • Actually simulating removals from the array is O(n²) for no benefit.

Reference solution

Python

from typing import List

def numberGame(nums: List[int]) -> List[int]:
    s = sorted(nums)
    out = []
    for i in range(0, len(s), 2):
        out.append(s[i + 1])
        out.append(s[i])
    return out

Java

public static int[] numberGame(int[] nums) {
    int[] s = nums.clone();
    Arrays.sort(s);
    int[] out = new int[s.length];
    for (int i = 0; i + 1 < s.length; i += 2) {
        out[i] = s[i + 1];
        out[i + 1] = s[i];
    }
    return out;
}

C++

vector<int> numberGame(vector<int>& nums) {
    vector<int> s = nums;
    sort(s.begin(), s.end());
    vector<int> out;
    for (size_t i = 0; i + 1 < s.size(); i += 2) {
        out.push_back(s[i + 1]);
        out.push_back(s[i]);
    }
    return out;
}

JavaScript

var numberGame = function(nums) {
    var s = nums.slice().sort(function(a, b) { return a - b; });
    var out = [];
    for (var i = 0; i + 1 < s.length; i += 2) {
        out.push(s[i + 1]);
        out.push(s[i]);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms