Skip to content

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.

Medium#2202
LeetCode Problem

Maximize the Topmost Element After K Moves

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

Input
nums = [5,2,2,4,0,6], k = 4
Output
5
Explanation

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

Input
nums = [2], k = 1
Output
-1
Explanation

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

1 <= nums.length <= 10^5
0 <= nums[i], k <= 10^9

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

  1. 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.
  2. 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.
  3. 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.
  4. 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

  1. The stack has six elements, so the parity rule does not apply.
  2. 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.
  3. Index k-1 = 3, value 4, is excluded: the fourth move necessarily disturbs it.
  4. Index k = 4 exists since 4 < 6 and gives 0 after four removals.
  5. 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.