LeetCode 2202 - Maximize the Topmost Element After K Moves

LeetCode Problem 2202

Difficulty: 🟡 Medium
Topics: Array, Greedy

Solution

Problem Understanding

In this problem, we are given a pile of integers represented as an array nums, where nums[0] is the current top element of the pile. We must perform exactly k moves, and in each move we are allowed to do one of two operations:

1. Remove the current top element from the pile.
2. Add back any previously removed element onto the top of the pile.

The goal is to maximize the value of the topmost element after exactly k moves.

The key detail is that once an element is removed, it becomes available forever for future add operations. We are not restricted to restoring the most recently removed element. We may choose any removed element.

The array size can be as large as 10^5, while k can be as large as 10^9. These constraints immediately tell us that we cannot simulate all possible move sequences. We need a direct mathematical or greedy observation.

Another important observation is that every remove operation exposes deeper elements in the stack. If we remove enough elements, a previously hidden element may become the new top without needing to add anything back.

The problem asks for the maximum possible top element after exactly k moves, not at most k moves. This distinction creates several important edge cases.

One especially tricky case occurs when the pile has only one element. If k is odd, the pile becomes empty after the last operation because removing and restoring alternate parity. In particular:

• nums = [x], k = 1 gives -1
• nums = [x], k = 3 can end with x
• nums = [x], k = 2 can also end with x

Another important case is when k = 0. No operations are allowed, so the answer is simply the current top element.

We also need to carefully handle situations where k exceeds the array length. Since removed elements can always be reinserted, large k values are often still manageable.

Approaches

Brute Force Approach

A brute force solution would try every possible sequence of operations. At each move, we can either:

• Remove the current top element, if the pile is non-empty.
• Reinsert any previously removed element.

This creates an enormous branching factor. The number of possible states grows exponentially with k.

For each recursive state, we would need to track:

• The current pile contents
• The set of removed elements
• The remaining number of moves

Although this guarantees correctness because every possible move sequence is explored, it is completely impractical for the given constraints. Even for small arrays and moderate values of k, the number of states becomes too large.

Optimal Greedy Observation

The crucial insight is that after exactly k moves, the final top element can only come from two sources:

1. One of the first k - 1 removed elements that we choose to place back on top.
2. The element naturally exposed after removing exactly k elements, which is nums[k].

Suppose we want some element to be the final top after exactly k moves.

If we place an element back onto the pile in the last move, then we must spend the previous k - 1 moves removing elements. Therefore, any of the first k - 1 elements can potentially become the final answer.

Alternatively, if we never add an element back during the last move, then after removing exactly k elements, the new top becomes nums[k].

Therefore, the answer is simply:

• The maximum value among the first k - 1 elements
• Or nums[k], if k < len(nums)

This reduces the problem to a simple greedy maximum computation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores all operation sequences
Optimal	O(min(n, k))	O(1)	Uses greedy observations about reachable top elements

Algorithm Walkthrough

1. First, handle the special case where the array contains only one element.

If len(nums) == 1, then the pile alternates between empty and non-empty depending on the parity of k.

• If k is odd, the pile ends empty, so return -1.
• If k is even, we can restore the element, so return nums[0].

2. Handle the case where k == 0.

No operations are performed, so the current top remains unchanged. Return nums[0]. 3. Compute the maximum among the first k - 1 elements.

These are the elements we could remove during the first k - 1 moves and then place back onto the top during the final move.

Specifically, we examine:

nums[0 : min(n, k - 1)]

4. If k < len(nums), also consider nums[k].

This represents the scenario where we spend all k moves removing elements. The element immediately below the removed section becomes the new top. 5. Return the larger value between:

• The best removable-and-reinsertable element
• The directly exposed element nums[k]

Why it works

After exactly k moves, the final operation determines the top element. If the last move is an insertion, then the inserted element must have been removed earlier, meaning it comes from the first k - 1 positions. If the last move is a removal, then exactly k elements have been removed and the new top becomes nums[k]. No other element can possibly appear on top after exactly k moves. Therefore, taking the maximum among these candidates always produces the optimal answer.

Python Solution

from typing import List

class Solution:
    def maximumTop(self, nums: List[int], k: int) -> int:
        n = len(nums)

        # Special case: only one element
        if n == 1:
            if k % 2 == 1:
                return -1
            return nums[0]

        # No moves
        if k == 0:
            return nums[0]

        answer = -1

        # Any of the first k - 1 elements can be reinserted
        limit = min(n, k - 1)

        for i in range(limit):
            answer = max(answer, nums[i])

        # If we remove exactly k elements,
        # nums[k] becomes the new top
        if k < n:
            answer = max(answer, nums[k])

        return answer

The implementation begins by checking the single-element edge case because it behaves differently from larger arrays. With one element, every removal empties the pile, so parity determines whether the pile can end non-empty.

Next, the code handles k == 0, where the initial top remains unchanged.

The variable answer stores the best achievable top value. We compute the maximum among the first k - 1 elements because those elements can be removed and later restored as the final move.

Finally, if k < n, the algorithm also considers nums[k], which represents the top after removing exactly k elements without restoring anything.

The implementation uses only a single loop and constant extra memory.

Go Solution

func maximumTop(nums []int, k int) int {
	n := len(nums)

	// Special case: only one element
	if n == 1 {
		if k%2 == 1 {
			return -1
		}
		return nums[0]
	}

	// No moves
	if k == 0 {
		return nums[0]
	}

	answer := -1

	// Maximum among first k - 1 elements
	limit := k - 1
	if limit > n {
		limit = n
	}

	for i := 0; i < limit; i++ {
		if nums[i] > answer {
			answer = nums[i]
		}
	}

	// Consider nums[k]
	if k < n && nums[k] > answer {
		answer = nums[k]
	}

	return answer
}

The Go implementation follows the same logic as the Python version. Since Go does not provide a built-in max function for integers, comparisons are done manually using if statements.

Slices in Go behave similarly to arrays for indexed access, so no special handling is required beyond bounds checking.

Integer overflow is not a concern because all values fit comfortably inside Go's standard int type.

Worked Examples

Example 1

nums = [5,2,2,4,0,6]
k = 4

We examine the first k - 1 = 3 elements:

Index	Value	Candidate Maximum
0	5	5
1	2	5
2	2	5

Current best candidate is 5.

Now consider nums[k] = nums[4] = 0.

Candidate Source	Value
Best removable element	5
Directly exposed element	0

Final answer:

max(5, 0) = 5

Example 2

nums = [2]
k = 1

The array contains only one element.

Since k is odd:

• Remove 2
• Pile becomes empty

No moves remain to restore the element.

Result:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(min(n, k))	We scan at most the first k - 1 elements
Space	O(1)	Only a few variables are used

The algorithm performs a single linear scan over at most min(n, k - 1) elements. No auxiliary data structures proportional to input size are allocated, so the space complexity remains constant.

Test Cases

sol = Solution()

# Provided examples
assert sol.maximumTop([5,2,2,4,0,6], 4) == 5  # example 1
assert sol.maximumTop([2], 1) == -1  # example 2

# No moves
assert sol.maximumTop([1,2,3], 0) == 1  # top remains unchanged

# Single element with even k
assert sol.maximumTop([7], 2) == 7  # can restore element

# Single element with odd k
assert sol.maximumTop([7], 3) == -1  # pile ends empty

# k smaller than length
assert sol.maximumTop([1,2,3,4], 2) == 3  # choose max between nums[0] and nums[2]

# k equals length
assert sol.maximumTop([1,2,3,4], 4) == 3  # cannot use nums[4]

# k greater than length
assert sol.maximumTop([3,5,2], 5) == 5  # reinsert maximum removed element

# Maximum at front
assert sol.maximumTop([10,1,1,1], 3) == 10  # keep largest removed value

# Maximum deeper in array
assert sol.maximumTop([1,2,10,4], 3) == 10  # restore deepest removed max

# All equal elements
assert sol.maximumTop([4,4,4,4], 2) == 4  # identical values

# Large k with multiple elements
assert sol.maximumTop([8,7,6], 100) == 8  # can always restore best removed element

Test	Why
[5,2,2,4,0,6], k=4	Validates standard mixed behavior
[2], k=1	Validates impossible non-empty result
[1,2,3], k=0	Validates no-operation scenario
[7], k=2	Validates single-element even parity
[7], k=3	Validates single-element odd parity
[1,2,3,4], k=2	Tests comparison between restored and exposed elements
[1,2,3,4], k=4	Tests boundary where nums[k] does not exist
[3,5,2], k=5	Tests very large k
[10,1,1,1], k=3	Tests preserving a large removed value
[1,2,10,4], k=3	Tests deeper maximum candidate
[4,4,4,4], k=2	Tests duplicate values
[8,7,6], k=100	Tests extreme move counts

Edge Cases

One important edge case occurs when the array contains only a single element. This case behaves differently because every removal empties the pile completely. If k is odd, the final move leaves the pile empty, making the answer -1. Many incorrect solutions forget this parity behavior and incorrectly return the original element.

Another tricky case is when k equals the array length. In this situation, nums[k] does not exist because removing all elements empties the pile. The only valid strategy is to restore one of the previously removed elements. The implementation handles this safely by checking if k < n before accessing nums[k].

A third subtle case happens when k is larger than the array size. A naive implementation might incorrectly assume the answer becomes invalid. However, because removed elements may be reinserted repeatedly, we can still end with a non-empty pile. The algorithm correctly handles this by considering the maximum among the removable elements and ignoring invalid indices.

Another edge case involves k = 0. Since no moves are allowed, the answer must simply be the original top element. Some implementations mistakenly attempt removal logic even though no operations occur.

Finally, duplicate values can also cause confusion. Since the problem only asks for the maximum possible top value, duplicates do not require special handling. The algorithm naturally works because it only tracks the largest reachable candidate.