We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Min Max Game

Number: 2386

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an array of integers, repeatedly construct a new array by taking pairs of numbers from the current array. For each pair, if the pair's index (in the new array) is even, insert the minimum of the two numbers; if odd, insert the maximum. Continue this process until only one number remains, and return that number.

Key Insights

  • The array length is always a power of 2, which guarantees that it can be halved continuously.
  • Use a simulation approach, iterating until the array is reduced to a single element.
  • Depending on the index of the pair’s position in the new array, choose the minimum (for even indices) or maximum (for odd indices).

Space and Time Complexity

Time Complexity: O(n) per round, and with each round halving the array length, the overall time complexity is O(n). Space Complexity: O(n) in the worst case for creating the new array each round.

Solution

This problem can be solved by simulating the process described. The algorithm involves iteratively constructing a new array from the current array:

  1. Create a new array of half the length.
  2. For each pair (nums[2i], nums[2i+1]) in the current array:
    • If the index i of the new array is even, set newNums[i] = min(nums[2i], nums[2i+1]).
    • If i is odd, set newNums[i] = max(nums[2i], nums[2i+1]).
  3. Replace the current array with the new array.
  4. Repeat until only one element remains, then return that element.

The simulation approach is straightforward since the array length is a power of 2; thus, the pairing always works perfectly without edge cases.

Code Solutions

# Python solution for the Min Max Game
def minMaxGame(nums):
    # Continue until the list is reduced to one element
    while len(nums) > 1:
        # Create a new list to store the results of the current round
        newNums = []
        # Process each pair in the current list
        for i in range(len(nums) // 2):
            # For even indexed positions use the min of the pair, else max.
            if i % 2 == 0:
                newNums.append(min(nums[2 * i], nums[2 * i + 1]))
            else:
                newNums.append(max(nums[2 * i], nums[2 * i + 1]))
        # Update nums to be the new list for the next iteration
        nums = newNums
    # Return the single remaining element
    return nums[0]

# Example usage:
print(minMaxGame([1, 3, 5, 2, 4, 8, 2, 2]))  # Expected output: 1
← Back to All Questions