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.
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.
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.
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.
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.
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).
| Approach | Complexity |
|---|---|
| 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. |
| Recursive Approach | Time Complexity: O(n log n) due to recursive decomposition at each step. |
| Simulation | — |
| 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. |
2293. Min Max Game (Leetcode Easy) • Programming Live with Larry • 1,057 views views
Watch 9 more video solutions →Practice Min Max Game with our built-in code editor and test cases.
Practice on FleetCode