Watch 10 video solutions for Min Max Game, a easy level problem involving Array, Simulation. This walkthrough by Programming Live with Larry has 1,057 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed integer array nums whose length is a power of 2.
Apply the following algorithm on nums:
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.i where 0 <= i < n / 2, assign the value of newNums[i] as min(nums[2 * i], nums[2 * i + 1]).i where 0 <= i < n / 2, assign the value of newNums[i] as max(nums[2 * i], nums[2 * i + 1]).nums with newNums.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 <= 10241 <= nums[i] <= 109nums.length is a power of 2.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 | Time | Space | When to Use |
|---|---|---|---|
| Iterative Simulation | O(n) | O(1) extra or O(n) | Best general solution. Directly simulates the game rules and is easiest to implement in interviews. |
| Recursive Reduction | O(n) | O(log n) | Useful when modeling the problem as repeated rounds or practicing recursion-based solutions. |