Skip to main content
Talentd

Min Max Game - Solution & Explanation

EasyArraySimulation17 min read
Practice this problem

Problem Statement

You are given a 0-indexed integer array nums whose length is a power of 2.

Apply the following algorithm on nums:

  1. Let n be the length of nums. If n == 1, end the process. Otherwise, create a new 0-indexed integer array newNums of length n / 2.
  2. For every even index i where 0 <= i < n / 2, assign the value of newNums[i] as min(nums[2 * i], nums[2 * i + 1]).
  3. For every odd index i where 0 <= i < n / 2, assign the value of newNums[i] as max(nums[2 * i], nums[2 * i + 1]).
  4. Replace the array nums with newNums.
  5. Repeat the entire process starting from step 1.

Return the last number that remains in nums after applying the algorithm.

 

Example 1:

Input: nums = [1,3,5,2,4,8,2,2]
Output: 1
Explanation: The following arrays are the results of applying the algorithm repeatedly.
First: nums = [1,5,4,2]
Second: nums = [1,4]
Third: nums = [1]
1 is the last remaining number, so we return 1.

Example 2:

Input: nums = [3]
Output: 3
Explanation: 3 is already the last remaining number, so we return 3.

 

Constraints:

  • 1 <= nums.length <= 1024
  • 1 <= nums[i] <= 109
  • nums.length is a power of 2.

Approach Overview

Problem Overview: You are given an array nums whose length is a power of two. Repeatedly reduce the array size by half. For each pair of elements, compute either min or max depending on the index: even indices take the minimum, odd indices take the maximum. Continue until only one number remains.

This is primarily a array reduction problem driven by rules. Each round constructs a smaller array derived from the previous one. The key observation: every iteration halves the array size, so the total amount of work across all rounds remains linear.

Approach 1: Iterative Simulation (Time: O(n), Space: O(1) or O(n))

Simulate the process exactly as described. While the array length is greater than 1, build the next round of values by iterating through pairs (nums[2*i], nums[2*i+1]). If i is even, store min(nums[2*i], nums[2*i+1]). If i is odd, store max(nums[2*i], nums[2*i+1]). Replace the current array with the newly computed one and repeat.

The insight is that although there are multiple rounds, the total number of operations across all rounds forms a geometric series: n + n/2 + n/4 + .... This sums to O(n). The implementation is straightforward and maps directly to the rules of the problem, making it the most practical solution. Space usage can be O(n) if a new array is created each round, or O(1) extra if the same array is reused.

Approach 2: Recursive Reduction (Time: O(n), Space: O(log n))

The same reduction logic can be expressed recursively. Create a helper function that receives the current array. If the array length is 1, return the element. Otherwise, construct the next reduced array using the same alternating min/max rule and recursively process it.

This approach models the game structure naturally: each recursive call represents one round of the game. Because the array size halves every time, recursion depth is log₂(n). The total number of element operations across all calls is still O(n). Recursion mainly improves conceptual clarity rather than performance.

Both approaches rely on simple iteration and pairwise comparisons, which makes this a classic simulation problem with heavy use of array indexing.

Recommended for interviews: The iterative simulation approach. Interviewers expect you to directly translate the rules into code and recognize that repeated halving keeps the total complexity at O(n). After presenting the iterative version, mentioning the recursive alternative shows a deeper understanding of the problem structure.

Approach 1: Iterative Approach

This approach involves iteratively reducing the array size by applying the min-max game rules until only one element remains. We use a while loop to repeatedly create a new array with half the size of the original array, filling it with minimum or maximum values as prescribed, until only one element is left.

This C solution involves modifying the original array in-place to avoid using extra space. We halve the array size in each iteration by applying the min-max conditions and overwriting the first half of the array with the new values. This continues until the array size becomes 1, at which point we return the single remaining element.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n), where n is the initial length of the array, because we process each level of the array log n times.
Space Complexity: O(1) since we are updating the input array in-place.

Try this approach in the editor →

Approach 2: Recursive Approach

This approach is based on recursively applying the min-max game until the array reduces to a single element. We define a recursive function that constructs the new array for each level of recursion and recurs until the base case of array size 1 is reached.

The C solution implements a recursive function that checks if the array size is 1 (base case). If not, it constructs a new half-sized array with the minimum or maximum values at each index and calls itself recursively with this new array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to recursive decomposition at each step.
Space Complexity: O(n log n) due to the stack space usage required by recursive calls.

Try this approach in the editor →

Approach 3: Simulation

According to the problem statement, we can simulate the entire process, and the remaining number will be the answer. In implementation, we do not need to create an additional array; we can directly operate on the original array.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Approach

Time Complexity: O(n log n), where n is the initial length of the array, because we process each level of the array log n times.
Space Complexity: O(1) since we are updating the input array in-place.

Recursive Approach

Time Complexity: O(n log n) due to recursive decomposition at each step.
Space Complexity: O(n log n) due to the stack space usage required by recursive calls.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative SimulationO(n)O(1) extra or O(n)Best general solution. Directly simulates the game rules and is easiest to implement in interviews.
Recursive ReductionO(n)O(log n)Useful when modeling the problem as repeated rounds or practicing recursion-based solutions.

Video Solution

Complete Weekly Contest 296 | Leetcode 2293 2294 2295 2296 |Partition Array Maximum Difference Is K • Coding Decoded • 1,496 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Min Max Game easy or hard?
Min Max Game is classified as an Easy problem. The challenge is mostly careful implementation of the alternating min/max rule while shrinking the array each round. Once the simulation pattern is recognized, the solution becomes straightforward.
How to solve Min Max Game in O(n)?
Iterate through the array in rounds. For each index i in the new array, compute min(nums[2*i], nums[2*i+1]) if i is even, otherwise compute max(nums[2*i], nums[2*i+1]). Replace the array with the reduced one and repeat until only one element remains. Because the array halves each round, the total runtime is linear.
What is the best approach for Min Max Game?
The iterative simulation approach is the best choice. You repeatedly build a new array where each element is either the min or max of a pair from the previous array. Because the array size halves each round, the total number of operations across all rounds is O(n) with constant or linear extra space depending on implementation.
What data structure is used in Min Max Game?
The problem primarily uses arrays. Each round reads values from the current array and writes results into a smaller array. No advanced data structures are required—only indexing, pair comparisons, and simple iteration.
What is the time complexity of Min Max Game?
The overall time complexity is O(n). Each round processes the current array once and reduces its size by half. The total work across rounds forms the series n + n/2 + n/4 + ... which sums to less than 2n.
Min Max Game Python or Java solution approach?
Both Python and Java implementations follow the same logic: iterate through pairs of elements, apply min for even indices and max for odd indices, and build the next reduced array. Continue until the array size becomes one. The algorithm runs in O(n) time in both languages.
Is Min Max Game asked at Google, Amazon, or Meta?
Min Max Game is an easy-level array simulation problem commonly used in coding interviews and practice platforms like LeetCode. Problems with iterative reduction and array simulation appear frequently in interviews at companies like Amazon and Google to evaluate basic problem-solving and implementation accuracy.

Ready to solve this problem?

Practice Min Max Game with our built-in code editor and test cases.

Practice on FleetCode
Previous

Elimination Game

Next

Find Triangular Sum of an Array