Get started

Minimum Number Game — Easy Problem & Solution

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

  • 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

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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue