Difficulty: Easy | Acceptance: 64.40% | Paid: No Topics: Array, Simulation
You are given a 0-indexed integer array nums whose length is a power of 2.
Apply the following algorithm on nums:
- 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.
- For every even index i in the range 0 <= i < n / 2, assign the value newNums[i] = min(nums[2 * i], nums[2 * i + 1]).
- For every odd index i in the range 0 <= i < n / 2, assign the value newNums[i] = max(nums[2 * i], nums[2 * i + 1]).
- Replace the array nums with newNums.
- Repeat the entire process starting from step 1.
Return the value that remains in nums after applying the algorithm.
- Examples
- Constraints
- Simulation with New Array
- In-Place Simulation
- Recursive Approach
Examples
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] <= 10^9
nums.length is a power of 2.
Simulation with New Array
Intuition Directly simulate the process by creating a new array in each iteration, applying min for even indices and max for odd indices until only one element remains.
Steps
- While array length is greater than 1, create a new array of half the size
- For each index in the new array, apply min for even indices and max for odd indices using pairs from the original array
- Replace the original array with the new array and repeat
class Solution:
def minMaxGame(self, nums: list[int]) -> int:
while len(nums) > 1:
new_nums = []
for i in range(len(nums) // 2):
if i % 2 == 0:
new_nums.append(min(nums[2 * i], nums[2 * i + 1]))
else:
new_nums.append(max(nums[2 * i], nums[2 * i + 1]))
nums = new_nums
return nums[0]Complexity
- Time: O(n log n) where n is the initial array length
- Space: O(n) for storing the new array
- Notes: Clear and intuitive but uses extra space for new arrays
In-Place Simulation
Intuition Optimize space by modifying the array in place instead of creating new arrays, overwriting elements from the beginning as we process pairs.
Steps
- Track the current effective length of the array
- For each iteration, overwrite elements at the beginning with computed values
- Halve the effective length after each pass until only one element remains
class Solution:
def minMaxGame(self, nums: list[int]) -> int:
n = len(nums)
while n > 1:
for i in range(n // 2):
if i % 2 == 0:
nums[i] = min(nums[2 * i], nums[2 * i + 1])
else:
nums[i] = max(nums[2 * i], nums[2 * i + 1])
n //= 2
return nums[0]Complexity
- Time: O(n log n) where n is the initial array length
- Space: O(1) extra space
- Notes: Optimal space complexity by reusing the input array
Recursive Approach
Intuition Use recursion to naturally handle the reduction process, where each recursive call processes one level of the algorithm.
Steps
- Base case: if array has only one element, return it
- Create a new array by applying min/max rules
- Recursively call the function on the new array
class Solution:
def minMaxGame(self, nums: list[int]) -> int:
if len(nums) == 1:
return nums[0]
new_nums = []
for i in range(len(nums) // 2):
if i % 2 == 0:
new_nums.append(min(nums[2 * i], nums[2 * i + 1]))
else:
new_nums.append(max(nums[2 * i], nums[2 * i + 1]))
return self.minMaxGame(new_nums)Complexity
- Time: O(n log n) where n is the initial array length
- Space: O(n) for recursion stack and new arrays
- Notes: Elegant but uses more space due to recursion overhead