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 <= 100nums.length is even1 <= nums[i] <= 100
Hints for Minimum Number Game
Hint 1
Both players always take the smallest remaining element, so the removal order is simply sorted order.
Hint 2
Round
tconsumes the sorted elements at positions2tand2t + 1.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
- Sort
numsascending intos. - Walk
iin steps of two and appends[i+1]thens[i]. - 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 outJava
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