Scale Engineer

Min Max Game

Easy
#2090Time: 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.
Data structures
Array

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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].

Walkthrough

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].

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];    }}

Complexity

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.

Trade-offs

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.

Solutions

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 ]; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem