LeetCode 2293 - Min Max Game

This problem asks us to repeatedly transform an array until only one number remains. At every round, we reduce the size of the array by half using alternating min and max operations on adjacent pairs.

leetcodeeasyarraysimulation

LeetCode Problem 2293

Difficulty: 🟢 Easy
Topics: Array, Simulation

Solution

Problem Understanding

This problem asks us to repeatedly transform an array until only one number remains. At every round, we reduce the size of the array by half using alternating min and max operations on adjacent pairs.

More specifically, we start with a 0-indexed array nums whose length is guaranteed to be a power of 2. During each iteration, we create a new array newNums of size n / 2, where n is the current length of nums.

For every index i in newNums:

  • If i is even, we take the minimum of the pair nums[2*i] and nums[2*i + 1].
  • If i is odd, we take the maximum of the pair nums[2*i] and nums[2*i + 1].

Once newNums is built, it replaces nums, and the process repeats until only one element remains. That final remaining value is the answer.

The input represents an integer array where each number participates in repeated pairwise reductions. The expected output is the final single integer left after all reductions have completed.

The constraints tell us several useful things about the problem:

  • nums.length is at most 1024, which is relatively small.
  • The length is always a power of 2, meaning repeated halving will always work cleanly until we reach a single element.
  • Each value can be as large as 10^9, but we are only comparing values, not performing arithmetic that risks overflow.

The most important edge case is when the array already contains only one element. In that case, no processing is needed, and we simply return that value immediately. Another possible source of bugs is correctly alternating between min and max based on the index in the new array, not the original array. The problem guarantees that the input length is valid, so we never need to worry about uneven pairing.

Approaches

Brute Force Approach

A brute-force solution directly simulates the problem statement exactly as written. At each round, we allocate a new array of size n / 2, iterate through adjacent pairs, apply either min or max depending on the parity of the new index, then replace the old array.

This approach is correct because it precisely follows the transformation rules defined in the problem. Every element of newNums is computed exactly as required, and repeating the process until one value remains guarantees the correct result.

Although this is technically a brute-force simulation, it is already efficient enough because the input size is very small. There is no need for more advanced optimization.

Optimal Approach

The key observation is that the problem naturally shrinks the input size by half during each iteration. Since the array length is always a power of 2, we can repeatedly simulate the process until only one element remains.

At every level:

  • We process all elements once.
  • The array becomes half as large.
  • The total amount of work forms a decreasing sequence:

$$n + \frac{n}{2} + \frac{n}{4} + \cdots$$

This geometric series sums to O(n), making the simulation very efficient.

We can further optimize space slightly by reusing the same variable reference for nums and assigning it to the newly constructed array after each round.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Directly simulates each transformation using new arrays
Optimal O(n) O(n) Same simulation, efficient because array size halves every round

Algorithm Walkthrough

  1. Start by checking the current array length. If the length is already 1, immediately return the only element because no operations are required.
  2. While the array contains more than one element, create a new empty array called new_nums whose size will eventually be half of the current array.
  3. Iterate through indices from 0 to (len(nums) // 2) - 1. Each index i corresponds to one pair of elements in the current array.
  4. For each i, compute the paired indices:
  • First element: nums[2 * i]
  • Second element: nums[2 * i + 1]
  1. Determine whether i is even or odd:
  • If i is even, append the smaller of the two values using min().
  • If i is odd, append the larger of the two values using max().
  1. After processing all pairs, replace nums with new_nums. This represents completing one full round of the game.
  2. Repeat the process until the array size becomes 1.
  3. Return the remaining element.

Why it works

The algorithm works because each iteration exactly reproduces the transformation described in the problem statement. Every position in the next array is computed using the correct operation, either min or max, based on the parity of the new index. Since the array length is guaranteed to be a power of 2, repeated halving eventually produces a single element, which is precisely the required result.

Python Solution

from typing import List

class Solution:
    def minMaxGame(self, nums: List[int]) -> int:
        while len(nums) > 1:
            new_nums = []

            for i in range(len(nums) // 2):
                first = nums[2 * i]
                second = nums[2 * i + 1]

                if i % 2 == 0:
                    new_nums.append(min(first, second))
                else:
                    new_nums.append(max(first, second))

            nums = new_nums

        return nums[0]

The implementation closely follows the algorithm described earlier. We repeatedly process the array while its length is greater than one.

Inside each iteration, we create a new array called new_nums. We loop through every pair of elements and decide whether to apply min or max based on whether the index i is even or odd.

Using variables first and second improves readability by making it clear which pair is being processed. After completing one round, we assign nums = new_nums, effectively shrinking the problem size.

Finally, when only one element remains, we return nums[0].

Go Solution

func minMaxGame(nums []int) int {
    for len(nums) > 1 {
        newNums := make([]int, len(nums)/2)

        for i := 0; i < len(nums)/2; i++ {
            first := nums[2*i]
            second := nums[2*i+1]

            if i%2 == 0 {
                if first < second {
                    newNums[i] = first
                } else {
                    newNums[i] = second
                }
            } else {
                if first > second {
                    newNums[i] = first
                } else {
                    newNums[i] = second
                }
            }
        }

        nums = newNums
    }

    return nums[0]
}

The Go implementation follows the same logic as the Python version but uses slices and explicit allocation with make().

Instead of dynamically appending elements, we preallocate newNums with length len(nums)/2 and directly assign values by index. This avoids repeated slice growth and is more idiomatic in Go.

There are no special concerns about integer overflow because the problem only compares values rather than performing arithmetic operations on large numbers. Since the constraints guarantee at least one element exists, accessing nums[0] at the end is always safe.

Worked Examples

Example 1

Input:

nums = [1,3,5,2,4,8,2,2]

First Iteration

i Pair Operation Result
0 (1, 3) min 1
1 (5, 2) max 5
2 (4, 8) min 4
3 (2, 2) max 2

New array becomes:

[1,5,4,2]

Second Iteration

i Pair Operation Result
0 (1, 5) min 1
1 (4, 2) max 4

New array becomes:

[1,4]

Third Iteration

i Pair Operation Result
0 (1, 4) min 1

New array becomes:

[1]

Final answer:

1

Example 2

Input:

nums = [3]

Since the array already contains one element, the loop never executes.

Final answer:

3

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each level processes all remaining elements, total work sums to n + n/2 + n/4 + ...
Space O(n) A temporary array of decreasing size is created during simulation

The time complexity is O(n) because each round processes every element once, but the array size halves after each iteration. The total work forms a geometric series whose sum is bounded by 2n.

The space complexity is O(n) because we allocate a temporary array during each iteration. Although only one such array exists at a time, its maximum size is proportional to the original input size.

Test Cases

solution = Solution()

assert solution.minMaxGame([1, 3, 5, 2, 4, 8, 2, 2]) == 1  # Example 1
assert solution.minMaxGame([3]) == 3  # Example 2, single element

assert solution.minMaxGame([1, 2]) == 1  # Smallest non-trivial input
assert solution.minMaxGame([2, 1]) == 1  # Min operation on first pair
assert solution.minMaxGame([5, 5]) == 5  # Equal values

assert solution.minMaxGame([1, 2, 3, 4]) == 1  # Multiple rounds
assert solution.minMaxGame([10, 1, 5, 20]) == 1  # Mix of min and max

assert solution.minMaxGame([1000000000]) == 1000000000  # Maximum value edge case

assert solution.minMaxGame([9, 8, 7, 6, 5, 4, 3, 2]) == 5  # Larger power-of-2 input
assert solution.minMaxGame([4, 4, 4, 4, 4, 4, 4, 4]) == 4  # Uniform values
Test Why
[1,3,5,2,4,8,2,2] Validates the official example
[3] Confirms single-element edge case
[1,2] Smallest reducible input
[2,1] Verifies minimum selection logic
[5,5] Ensures equal-value comparisons work
[1,2,3,4] Tests multiple rounds of reduction
[10,1,5,20] Verifies alternating min/max behavior
[1000000000] Tests maximum allowed number
[9,8,7,6,5,4,3,2] Tests deeper recursive reductions
[4,4,4,4,4,4,4,4] Confirms stable behavior with identical values

Edge Cases

Single Element Array

An input such as nums = [3] is an important edge case because no transformation should happen. A naive implementation might still attempt to create a new array or process pairs, leading to indexing errors. This implementation correctly handles the case because the while len(nums) > 1 condition immediately fails, and the single element is returned.

Minimum Valid Length

Arrays with exactly two elements, such as [1, 2], can reveal indexing mistakes. Since only one pair exists, only the even-index rule should apply, meaning we must use min. The implementation handles this correctly because i = 0 is even.

Equal Values

Inputs like [5, 5] or arrays containing repeated numbers can expose logic bugs where comparisons incorrectly favor one side. Since min(5, 5) and max(5, 5) both return 5, the implementation behaves consistently and preserves correctness.

Multiple Reduction Levels

Larger inputs such as [1,3,5,2,4,8,2,2] require several rounds of shrinking. Bugs often appear when reassigning the working array between iterations. This implementation avoids that issue by replacing nums with new_nums after each round, ensuring each level operates on the latest transformed array.