[Solution] Min Max Game – LeetCode Weekly Contest 296

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

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] <= 109
• nums.length is a power of 2.

Solution:

Space Complexity: O(1)

class Solution {
public:
    int minMaxGame(vector<int>& nums) {
        
        int n(size(nums));
        for (; n>1; n-=n/2) {
            for (int i=0; i<n/2; i++) {
                nums[i] = ((i % 2 == 1) ? max(nums[2*i], nums[2*i+1]) : min(nums[2*i], nums[2*i+1]));
            }
        }
        return nums[0];
    }
};

Space Complexity: O(n)

class Solution {
public:
    int minMaxGame(vector<int>& nums) {
        
        while (size(nums) != 1) {
            
            vector<int> temp;
            for (int i=0; i<size(nums)/2; i++) {
                temp.push_back((i % 2 == 1) ? max(nums[2*i], nums[2*i+1]) : min(nums[2*i], nums[2*i+1]));
            }
            nums = temp;
        }
        return nums[0];
    }
};

class Solution {
    public int minMaxGame(int[] a) {
    for(int n= a.length; n>1 ; n-=(n/2)){
        for(int i=0;i<n/2;i++) 
		    a[i]= (i%2)==1? Math.max(a[2 * i], a[2 * i + 1]) : Math.min(a[2 * i], a[2 * i + 1]);   
    }
    return a[0];
}
}

Time Complexity: O(n)

– No need to create new array.
– It can be seen that changes can be mae within same array.
– The changed elements are never called again so their positions are useless and we use those vacant indexes.

class Solution:
    def minMaxGame(self, a: List[int]) -> int:
        
        def solve(n):
            if n==1:
                return
            for i in range(n//2):
                if i%2:
                    a[i] = max (a[2*i], a[2*i+1])
                else:
                    a[i] = min (a[2*i], a[2*i+1])
            solve(n//2)
            return
        solve(len(a))
        return a[0]

Happy Learning – If you require any further information, feel free to contact me.