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:
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 <= 1050 <= nums[i], k <= 109In #2202 Maximize the Topmost Element After K Moves, you are allowed to repeatedly remove the top element of a stack-like array or add back a previously removed element. The goal is to maximize the value of the top element after exactly k moves. Because each move changes which elements are available to return to the stack, the key idea is to reason about the set of elements that could potentially become the top after performing up to k operations.
A common strategy uses a greedy observation: during the first few removals, you expose deeper elements and collect candidates that could later be pushed back. The optimal top element must come from the elements removed earlier or from the next untouched element once enough removals are made. Carefully handling edge cases—such as when the array has a single element or when the number of moves forces the stack to become empty—is crucial.
The algorithm typically scans a limited prefix of the array to find the best candidate value while respecting operation constraints. This leads to an efficient solution with linear or near-linear time relative to the number of considered elements and constant extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy scan of candidate elements | O(n) (often limited to O(k)) | O(1) |
Ashish Pratap Singh
Use these hints if you're stuck. Try solving on your own first.
For each index i, how can we check if nums[i] can be present at the top of the pile or not after k moves?
For which conditions will we end up with an empty pile?
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
While the exact problem may not always appear, similar stack and greedy reasoning questions are common in FAANG-style interviews. Understanding how operations affect available choices and maximizing outcomes is a frequently tested pattern.
The problem conceptually behaves like a stack, but the input is provided as an array. Most solutions operate directly on the array while tracking the maximum among removable elements, so no additional complex data structures are required.
Edge cases arise when the array has only one element or when the number of moves forces the stack to become empty. In these situations, certain sequences of operations may leave no element on top, which changes the expected result.
The optimal approach uses greedy reasoning. By analyzing which elements can be removed and potentially pushed back within k moves, you can determine the largest value that could end up on top. This usually involves scanning the first few elements and carefully handling edge cases.