Maximize the Topmost Element After K Moves

Problem Description

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: remove the topmost element of the pile if it is not empty, or add any one of the previously removed elements back onto the pile, making it 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. If it is not possible to obtain a non-empty pile after k moves, return -1.

Key Insights

• If k is greater than or equal to the length of nums, you can always return the maximum element in nums since you can remove all elements and add the maximum back.
• If k is less than the length of nums, you can only remove up to k elements. The remaining elements can be examined to determine the maximum possible topmost element.
• Special case: If k equals the length of nums and the array has only one element, you will end up with an empty pile after all moves.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can follow these steps:

1. If k is greater than or equal to the length of nums, return the maximum element in nums.
2. If k is less than the length of nums, iterate through the first k + 1 elements of the array and track the maximum value found, since these elements can either remain or be removed.
3. If k is equal to the length of nums and there is only one element, return -1.

This approach uses a simple linear scan to find the maximum value which can be the topmost element after k moves.

Code Solutions