Teaching Kids Programming – Algorithms to Solve a Min Max Binary Tree Game (Queue, Recursion, In-place)

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a 0-indexed integer array nums whose length is a power of 2.

Min Max Binary Tree

Apply the following algorithm on nums:

1. 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.
2. For every even index i where 0 <= i < n / 2, assign the value of newNums[i] as min(nums[2 * i], nums[2 * i + 1]).
3. For every odd index i where 0 <= i < n / 2, assign the value of newNums[i] as max(nums[2 * i], nums[2 * i + 1]).
4. Replace the array nums with newNums.
5. Repeat the entire process starting from step 1.

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 <= 1024
1 <= nums[i] <= 10^9
nums.length is a power of 2.

Recursion Algorithm to Solve the Min Max Binary Tree Game

The Recursive Idea is to apply the simulation process, and recursively solve a smaller tree. With each recursion call, the size of the array (the leaves nodes) is reduced to its half until we have only one leaf node which we should just return itself.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def minMaxGame(self, nums: List[int]) -> int:
        def f(arr):
            n = len(arr)
            if n == 1:
                return arr
            ans = []
            g = min
            for i in range(0, n, 2):
                ans.append(g(arr[i], arr[i + 1]))
                g = max if g == min else min
            return f(ans)
        return f(nums)[0]

class Solution:
    def minMaxGame(self, nums: List[int]) -> int:
        def f(arr):
            n = len(arr)
            if n == 1:
                return arr
            ans = []
            g = min
            for i in range(0, n, 2):
                ans.append(g(arr[i], arr[i + 1]))
                g = max if g == min else min
            return f(ans)
        return f(nums)[0]

The min and max takes turn, and we can use the cycle function from itertools to make it pythonic way! The cycle returns an endless iterator which we can use next() to advance indefinitely.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def minMaxGame(self, nums: List[int]) -> int:
        def f(arr):
            n = len(arr)
            if n == 1:
                return arr
            ans = []
            g = cycle((min, max))
            for i in range(0, n, 2):
                ans.append(next(g)(arr[i], arr[i + 1]))
            return f(ans)
        return f(nums)[0]

class Solution:
    def minMaxGame(self, nums: List[int]) -> int:
        def f(arr):
            n = len(arr)
            if n == 1:
                return arr
            ans = []
            g = cycle((min, max))
            for i in range(0, n, 2):
                ans.append(next(g)(arr[i], arr[i + 1]))
            return f(ans)
        return f(nums)[0]

The time complexity is O(LogN) as it takes Log(N) steps to reduce N leaves to 1. The space complexity is O(N) as we are using additional array and recursion.

Solve the Min Max Binary Tree Game using Queue

We can turn the numbers into a queue, and each iteration we remove/pop two elements from the queue, and apply the min/max operation and push the result back to the queue.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def minMaxGame(self, nums: List[int]) -> int:
        q = deque(nums)
        while len(q) > 1:
            n = len(q)
            g = cycle((min, max))
            for _ in range(n//2):
                a, b = q.popleft(), q.popleft()
                q.append(next(g)(a, b))
        return q[0]

class Solution:
    def minMaxGame(self, nums: List[int]) -> int:
        q = deque(nums)
        while len(q) > 1:
            n = len(q)
            g = cycle((min, max))
            for _ in range(n//2):
                a, b = q.popleft(), q.popleft()
                q.append(next(g)(a, b))
        return q[0]

The time complexity is O(LogN), the space complexity is O(N) as we need to store all numbers (leaves of the given binary tree) in the queue.

Solve the Min Max Binary Tree Game In-place O(1) space

We can do this in place without allocating additional space. We can change the numbers in place. The nums[i] is the result of nums[2*i] and nums[2*i+1].

1
2
3
4
5
6
7
8
9

class Solution:
    def minMaxGame(self, nums: List[int]) -> int:
        n = len(nums)
        while n > 1:
            g = cycle((min, max))
            for i in range(n//2):
                nums[i] = next(g)(nums[2*i], nums[2*i+1])
            n >>= 1
        return nums[0]

class Solution:
    def minMaxGame(self, nums: List[int]) -> int:
        n = len(nums)
        while n > 1:
            g = cycle((min, max))
            for i in range(n//2):
                nums[i] = next(g)(nums[2*i], nums[2*i+1])
            n >>= 1
        return nums[0]

The time complexity is O(LogN) where N is the number of elements in the original array and the space complexity is O(1).

–EOF (The Ultimate Computing & Technology Blog) —