# Min Max Game
**Difficulty:** EASY
[External](https://leetcode.com/problems/min-max-game)
Canonical: https://scaleengineer.com/dsa/problems/min-max-game
**Data structures:** Array
---
## Problem
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:**

![](https://assets.glich.co/dsa/min-max-game/image0.png) 

**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`.

# Approaches
## Simulation with Extra Space
This approach directly simulates the process described in the problem statement. In each step of the algorithm, we create a new array to store the results of the min/max operations. We repeat this process, halving the array size each time, until only one element remains.
**Time:** O(N), where `N` is the initial length of `nums`. The total number of operations is the sum of the lengths of the arrays at each step: `N/2 + N/4 + ... + 1`, which is a geometric series that sums to `N - 1`. Thus, the complexity is linear in the size of the input array. · **Space:** O(N). In the first step, we create a new array of size `N/2`. In subsequent steps, we create smaller arrays, but the space is dominated by the largest temporary array. We also make an initial copy of `nums`, which takes `O(N)` space.
**Pros:** Simple to understand and implement as it directly follows the problem description.; Does not modify the original input array (if we make a copy first).
**Cons:** Uses extra space to store the intermediate arrays, which can be significant for a very large input array.
### Explanation
We start a loop that continues as long as the length of the array `nums` is greater than 1. Inside the loop, we first get the current length `n`. We create a new temporary array, `newNums`, with a size of `n / 2`. We then iterate from `i = 0` to `n / 2 - 1`. For each `i`, if `i` is even, we calculate `min(nums[2 * i], nums[2 * i + 1])` and store it in `newNums[i]`. If `i` is odd, we calculate `max(nums[2 * i], nums[2 * i + 1])` and store it in `newNums[i]`. After filling `newNums`, we replace the original `nums` array with `newNums`. The loop continues with the new, smaller `nums` array. Once the loop terminates (when `nums` has only one element), we return that single element, `nums[0]`. 

```java
import java.util.Arrays;

class Solution {
    public int minMaxGame(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }

        int[] currentNums = Arrays.copyOf(nums, n);

        while (n > 1) {
            n /= 2;
            int[] newNums = new int[n];
            for (int i = 0; i < n; i++) {
                if (i % 2 == 0) {
                    newNums[i] = Math.min(currentNums[2 * i], currentNums[2 * i + 1]);
                } else {
                    newNums[i] = Math.max(currentNums[2 * i], currentNums[2 * i + 1]);
                }
            }
            currentNums = newNums;
        }
        return currentNums[0];
    }
}
```
### Algorithm
- Initialize a variable `n` with the length of `nums`.
- If `n` is 1, return `nums[0]`.
- Create a copy of the input array, let's call it `currentNums`.
- Start a `while` loop that continues as long as `n > 1`.
- Inside the loop, update `n` to `n / 2`.
- Create a new integer array `newNums` of size `n`.
- Loop from `i = 0` to `n - 1`:
    - If `i` is even, set `newNums[i] = min(currentNums[2 * i], currentNums[2 * i + 1])`.
    - If `i` is odd, set `newNums[i] = max(currentNums[2 * i], currentNums[2 * i + 1])`.
- After the inner loop, assign `newNums` to `currentNums`.
- When the `while` loop finishes, `currentNums` will contain a single element. Return `currentNums[0]`.

## In-place Simulation
This approach optimizes the simulation by performing the operations directly on the input array, thus avoiding the need to create new arrays in each step. This significantly reduces the space complexity.
**Time:** O(N), where `N` is the initial length of `nums`. Similar to the first approach, the total number of min/max operations is `N/2 + N/4 + ... + 1 = N - 1`. The time complexity is linear. · **Space:** O(1). This approach modifies the array in-place and does not require any additional data structures that scale with the input size. The space used is constant.
**Pros:** Highly space-efficient, using only constant extra space.; Still relatively simple to implement.
**Cons:** Modifies the input array, which might not be desirable in some contexts. If the original array needs to be preserved, a copy must be made first, which would negate the space advantage.
### Explanation
We can observe that when we compute the new values for the next iteration, the `i`-th new value depends on `nums[2*i]` and `nums[2*i+1]`. Since `i` is always less than `2*i` and `2*i+1` (for `i >= 0`), we can overwrite the first half of the array without losing any data needed for the current step's calculations. We use a variable, say `n`, to keep track of the current effective size of the array. Initially, `n` is the length of `nums`. The simulation proceeds in a loop that runs as long as `n > 1`. In each iteration, we first halve `n`. Then, we loop from `i = 0` to the new `n - 1`. Inside this inner loop, we calculate the new value based on the min/max rule and store it back into `nums[i]`. After the inner loop completes, the first `n` elements of `nums` contain the new set of values, and `n` has been updated to reflect the new size. The process repeats until `n` becomes 1. The final result is then `nums[0]`. 

```java
class Solution {
    public int minMaxGame(int[] nums) {
        int n = nums.length;
        while (n > 1) {
            n /= 2;
            for (int i = 0; i < n; i++) {
                if (i % 2 == 0) {
                    nums[i] = Math.min(nums[2 * i], nums[2 * i + 1]);
                } else {
                    nums[i] = Math.max(nums[2 * i], nums[2 * i + 1]);
                }
            }
        }
        return nums[0];
    }
}
```
### Algorithm
- Initialize a variable `n` with the length of the input array `nums`.
- Start a `while` loop that continues as long as `n > 1`.
- Inside the loop, update `n` to `n / 2`. This new `n` is the size of the array for the next stage.
- Loop from `i = 0` to `n - 1`:
    - If `i` is even, update `nums[i]` with `min(nums[2 * i], nums[2 * i + 1])`.
    - If `i` is odd, update `nums[i]` with `max(nums[2 * i], nums[2 * i + 1])`.
- The `while` loop continues, effectively processing a smaller prefix of the `nums` array in each iteration.
- When the loop terminates (`n` is 1), the final result is stored in `nums[0]`. Return `nums[0]`.

# Solutions
### Java

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

### CPP

```cpp
class Solution { public: int minMaxGame ( vector < int >& nums ) { for ( int n = nums . size (); n > 1 ;) { n >>= 1 ; for ( int i = 0 ; i < n ; ++ i ) { int a = nums [ i << 1 ], b = nums [ i << 1 | 1 ]; nums [ i ] = i % 2 == 0 ? min ( a , b ) : max ( a , b ); } } return nums [ 0 ]; } };
```

### Python

```python
class Solution:
    def minMaxGame(self, nums: List[int]) -> int: n = len(nums) while n > 1: n >>= 1 for i in range(n): a, b = nums[i << 1], nums[i << 1 | 1] nums[i] = min(a, b) if i % 2 == 0 else max(a, b) return nums[0]

```