Practice Maximize the Topmost Element After K Moves
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Problem Statement
nums describes a stack with nums[0] on top. A move either removes the top when nonempty or returns any previously removed entry to the top. After exactly k moves, maximize the top value and return it. Return -1 if no legal sequence leaves a nonempty stack.
Source: Maximize the Topmost Element After K Moves on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
nums = [5,2,2,4,0,6], k = 4
5
Use three moves to remove the values 5, 2 and 2, then use the fourth move to return 5 to the top. This leaves a nonempty stack with top 5. Alternatively, four removals expose the original value at index 4, which is 0. In four moves, a value restored on the final move must come from the first three positions; otherwise there is not enough time both to reach it and put it back. The deeper 6 is therefore unavailable, making 5 optimal.
# Example 2
nums = [2], k = 1
-1
There is only one value and exactly one move must be made. Initially no removed value is available to put back, so the only legal move removes 2 and leaves the stack empty. Stopping without moving would violate the exact move count. Thus no nonempty final stack is possible and the result is -1. For a one-element stack, removal and replacement must alternate, so odd move counts end empty.
Constraints
How to solve Maximize the Topmost Element After K Moves
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
After exactly k moves the top can be any of the first k-1 elements, removed early and returned on the final move with spare moves wasted in between, or the element at index k, exposed by k straight removals. Index k-1 is never reachable, and a one-element stack reduces to the parity of k.
Why brute force is not enough
Simulating every sequence of k removals and re-insertions branches exponentially, and with nums.length up to 10^5 and k up to 10^9 even a state search over stack depth and removed set is hopeless.
Approach
- Handle a single-element stack first: moves must alternate remove and put back, so an odd k leaves it empty (answer -1) and an even k restores the element.
- For two or more elements, any index i at most k-2 can finish on top: remove the first i+1 elements, burn leftover moves by popping and re-pushing another removed element in pairs, or with one extra removal if an odd number remains, and return nums[i] on the last move.
- Index k-1 is impossible because after k-1 removals the final move must remove or cover it. Index k is reachable only by k straight removals, which needs k < nums.length.
- Return the maximum over indices 0 through min(k-2, n-1), compared with nums[k] when it exists.
Walkthrough of Example 1
nums = [5,2,2,4,0,6], k = 4 → 5
- The stack has six elements, so the parity rule does not apply.
- Indices 0 through k-2 = 2 hold 5, 2 and 2; the best is 5, reached by removing 5, 2, 2 and returning 5 on move four.
- Index k-1 = 3, value 4, is excluded: the fourth move necessarily disturbs it.
- Index k = 4 exists since 4 < 6 and gives 0 after four removals.
- The answer is max(5, 0) = 5.
Time and space
Time O(min(n, k)) · Space O(1). One pass over at most the first k-1 of the n elements, keeping only a few scalars.
Interview pitfalls
- Missing the single-element case: with n = 1 and even k the answer is nums[0], and with odd k it is -1.
- Including index k-1 in the candidate range, an off-by-one that no legal sequence can realize.
- Reading nums[k] without checking k < n, or looping k times instead of min(k-1, n) times when k is near 10^9.
- Imposing a parity condition on stacks of size two or more; an odd surplus of moves is absorbed by one extra removal.
Follow-up questions interviewers ask
- What changes if returned elements must come back in reverse removal order, like a true undo stack?
- How would you answer many k values for the same stack quickly, for example with a prefix maximum array?
- Can you output a concrete sequence of k moves achieving the maximum?
Related LeetCode Problems
Practice more problems similar to Maximize the Topmost Element After K Moves.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.