Maximize the Topmost Element After K Moves

Maximize the Topmost Element After K Moves

What is this problem about?

You are given a 0-indexed integer array nums representing a pile of cards, and an integer k. In a single move, you can either remove the top card of the pile (if it's not empty) or take one card you previously removed and place it back on top of the pile. After exactly k moves, your goal is to maximize the value of the card sitting at the very top of the pile. If the pile is empty after k moves, return -1.

Why is this asked in interviews?

This is a pure logic and edge-case brainteaser. Interviewers ask it because it requires almost no code but demands airtight logical reasoning. It tests whether a candidate can break down a game-theory simulation into discrete mathematical scenarios based on the relationship between k (moves) and N (array length).

Algorithmic pattern used

This utilizes Greedy Deduction. There is no array mutation needed; you just calculate the answer based on k. Consider what happens in k moves:

1. You can safely remove the top k - 1 elements. On the $k$-th move, you can place the largest element you just removed back on top.
2. Alternatively, you can just remove k elements, leaving the element originally at index k sitting on the top of the pile.
3. Therefore, the answer is the maximum between: the maximum element in nums[0...k-2] AND the element at nums[k]. Notice we skip index k-1 because if we remove it on move k, it's not on top, and we don't have a move left to put it back!

Example explanation

Array: [5, 2, 2, 4, 0, 6], k = 4. Scenario 1: We use 3 moves to remove 5, 2, 2. On the 4th move, we put 5 back on top. The top is 5. Scenario 2: We use 4 moves to remove 5, 2, 2, 4. The element now on top is 0. We take the maximum of the elements we can put back (max(5, 2, 2) = 5) and the element exposed (0). The maximum is 5. Wait, what about the 4 at index 3 (k-1)? If we remove 5, 2, 2, we are at move 3. The 4 is exposed. If we want 4 on top, we just stop... but we must make exactly 4 moves! If we remove 4, the top is 0. We can't put 4 back because we used our 4th move to remove it. So 4 is a "dead zone" and can never be the final top element!

Common mistakes candidates make

The biggest trap is failing edge cases.

• If n == 1 and k is odd, you remove the only element on move 1, put it back on move 2, remove it on move 3... it will always be empty on an odd move! Return -1.
• If k > n, you have enough moves to remove every single element and still have moves left over. You can easily just drop the absolute maximum element of the entire array back on top at the very end.

Interview preparation tip

When an interview question asks for the state of a system "after exactly K moves" involving reversible actions, always map out the edge cases explicitly: k == 0, n == 1, k == n, and k > n. Writing these out as early if statements guarantees you won't fail the hidden test cases and clarifies the remaining generic logic.