{x}
blog image

Maximize the Topmost Element After K Moves

You are given a 0-indexed integer array nums representing the contents of a pile, where nums[0] is the topmost element of the pile.

In one move, you can perform either of the following:

  • If the pile is not empty, remove the topmost element of the pile.
  • If there are one or more removed elements, add any one of them back onto the pile. This element becomes the new topmost element.

You are also given an integer k, which denotes the total number of moves to be made.

Return the maximum value of the topmost element of the pile possible after exactly k moves. In case it is not possible to obtain a non-empty pile after k moves, return -1.

 

Example 1:

Input: nums = [5,2,2,4,0,6], k = 4
Output: 5
Explanation:
One of the ways we can end with 5 at the top of the pile after 4 moves is as follows:
- Step 1: Remove the topmost element = 5. The pile becomes [2,2,4,0,6].
- Step 2: Remove the topmost element = 2. The pile becomes [2,4,0,6].
- Step 3: Remove the topmost element = 2. The pile becomes [4,0,6].
- Step 4: Add 5 back onto the pile. The pile becomes [5,4,0,6].
Note that this is not the only way to end with 5 at the top of the pile. It can be shown that 5 is the largest answer possible after 4 moves.

Example 2:

Input: nums = [2], k = 1
Output: -1
Explanation: 
In the first move, our only option is to pop the topmost element of the pile.
Since it is not possible to obtain a non-empty pile after one move, we return -1.

 

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i], k <= 109

Solution Explanation

The problem asks to find the maximum value that can be at the top of the pile after k moves. Each move can either remove the top element or add back a previously removed element.

The solution leverages several observations to efficiently solve this problem:

  1. Base Cases:

    • If k is 0, the top element remains unchanged.
    • If there's only one element (len(nums) == 1) and k is odd, it's impossible to have an element at the top after removing the only element an odd number of times. If k is even, the top element remains the same.

  2. Optimal Strategy: The optimal strategy involves removing the top k-1 elements if possible and then placing the largest of those removed elements back on the pile (if k-1 < len(nums)). Alternatively, if k is less than the length of nums, the element at index k will be the top element after k moves.

  3. Algorithm:

    • Handle the base cases.
    • If k-1 is less than the length of the array, find the maximum element among the first k-1 elements. This is the maximum possible top element if we add one of the removed elements back.
    • If k is less than the length of the array, compare the maximum element found above with the element at index k (the element that becomes the top after removing k elements).
    • Return the larger of these two values (or -1 if no element remains).

Time and Space Complexity Analysis

Time Complexity: O(min(k, n)), where n is the length of nums. The algorithm iterates through at most min(k-1, n) elements to find the maximum among the removed elements.

Space Complexity: O(1). The algorithm uses only a constant amount of extra space.

Code Explanation (Python)

class Solution:
    def maximumTop(self, nums: List[int], k: int) -> int:
        if k == 0:
            return nums[0]
        n = len(nums)
        if n == 1:
            if k % 2:
                return -1
            return nums[0]
        ans = max(nums[: k - 1], default=-1) #Find max among the first k-1 elements
        if k < n:
            ans = max(ans, nums[k]) #Compare with the element at index k
        return ans

The python code directly implements the algorithm described above. The max(nums[: k - 1], default=-1) line efficiently handles the case where k-1 might be larger than the array length, providing a default value of -1 if the slice is empty.

The other languages (Java, C++, Go) follow a similar logic, with minor syntactic differences to adapt to each language's specific features. The core algorithm and complexity analysis remain consistent across all the provided implementations.