Problem Description
You are given a 0-indexed integer array nums whose length is a power of 2. Apply an algorithm to repeatedly reduce the array until only one number remains. The reduction involves creating a new array where each element is derived from the minimum and maximum of pairs of elements from the previous array.
Key Insights
- The reduction process alternates between taking the minimum and maximum of adjacent pairs.
- For an even index in the new array, the value is the minimum of the two corresponding values in the original array.
- For an odd index in the new array, the value is the maximum of the two corresponding values in the original array.
- The process continues until only one element remains, which is the final answer.
Space and Time Complexity
Time Complexity: O(n) for each reduction step, where n is the current length of the array. Since the array length halves with each step, the total time complexity is O(n log n). Space Complexity: O(n) for the new array created in each step.
Solution
The algorithm uses a loop to repeatedly create a new array, newNums, based on the current values in nums. It processes pairs of elements to compute the minimum for even indices and the maximum for odd indices. This continues until nums is reduced to a single element, which is returned as the final result.