Min Max Game - Practice Coding Problems

Min Max Game - Problem

Array Simulation Easy

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

Return the last number that remains in nums after applying the algorithm.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,3,5,2,4,8,2,2]

› Output: 1

💡 Note: Round 1: [min(1,3), max(5,2), min(4,8), max(2,2)] = [1,5,4,2]. Round 2: [min(1,5), max(4,2)] = [1,4]. Round 3: min(1,4) = 1

Example 2 — Smaller Array

$ Input: nums = [3]

› Output: 3

💡 Note: Array has only one element, so return it directly

Example 3 — Two Elements

$ Input: nums = [9,3]

› Output: 3

💡 Note: Even index 0: min(9,3) = 3

Constraints

1 ≤ nums.length ≤ 1024
nums.length is a power of 2
1 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

Start with power-of-2 length array

Apply Rules

Even indices take min, odd indices take max of pairs

Final Result

Continue until one element remains

Key Takeaway

🎯 Key Insight: The algorithm simulates a tournament where even positions favor smaller values (min) and odd positions favor larger values (max)

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The Min-Max Game requires simulating the tournament-style elimination process. Each round, we pair adjacent elements and apply min for even indices, max for odd indices. The key insight is that we can either create new arrays each round or modify in-place. Best approach is in-place simulation with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Simulation	O(n)	O(n)	Simulate each round of the min-max game until one element remains
In-Place Simulation	O(n)	O(1)	Simulate the game using in-place array modification to save space

Simulation — Algorithm Steps

While array has more than 1 element
Create new array of half size
For even indices: take min of pairs
For odd indices: take max of pairs
Replace original array

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Array

Start with the input array

Round 1

Apply min/max rules to pairs

Final Result

Continue until one element remains

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int size) {
    int* current = (int*)malloc(size * sizeof(int));
    for (int i = 0; i < size; i++) {
        current[i] = nums[i];
    }
    
    int currentSize = size;
    
    while (currentSize > 1) {
        int newSize = currentSize / 2;
        int* newNums = (int*)malloc(newSize * sizeof(int));
        
        for (int i = 0; i < newSize; i++) {
            if (i % 2 == 0) {  // even index
                newNums[i] = (current[2 * i] < current[2 * i + 1]) ? current[2 * i] : current[2 * i + 1];
            } else {  // odd index
                newNums[i] = (current[2 * i] > current[2 * i + 1]) ? current[2 * i] : current[2 * i + 1];
            }
        }
        
        free(current);
        current = newNums;
        currentSize = newSize;
    }
    
    int result = current[0];
    free(current);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple JSON array parsing
    int nums[1000];
    int size = 0;
    
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* token = strtok(ptr, ",]\n");
        while (token && size < 1000) {
            nums[size++] = atoi(token);
            token = strtok(NULL, ",]\n");
        }
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

We process n elements, then n/2, then n/4, etc. Total: n + n/2 + n/4 + ... = 2n = O(n)

✓ Linear Growth

Space Complexity

O(n)

At each step we create a new array, maximum size is n/2

⚡ Linearithmic Space

25.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler