Abstract / Summary

Given a list of integers and a number of moves, repeatedly take the highest value and move it to the top to maximize the top element after all moves.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 24% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Greedy

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of determining the maximum possible value that can appear on the top of a stack after performing exactly k operations. Each operation may either remove the current top element or insert a previously removed element back onto the stack. The algorithm works directly on the input list nums, treating its first element as the top of the stack, and returns the optimal top value or -1 when the stack would be empty after the required number of moves.

Key Steps

Determine the length of the input

size = len(nums)

The algorithm begins by capturing the number of elements in the list. This value is used throughout the subsequent conditional logic to decide which execution path to follow.

Handle the single-element scenario

if size == 1:
    return -1 if k & 1 else nums[0]

When the list contains only one element, the only possible outcome depends on the parity of k. An odd number of operations forces the sole element to be removed, leaving the stack empty, which is signaled by returning -1. An even number of operations allows the element to be removed and then re-inserted, preserving it as the top.

Short-circuit for very small k

if k <= 1:
    return nums[k]

If k is zero, the top of the stack remains unchanged, and the function returns nums[0]. If k equals one, the only permissible move is to pop the current top, making the second element (nums[1]) the new top. This direct indexing avoids any further computation.

Compute the largest value among the first k-1 elements

high = max(nums[:k - 1])

When more than one operation is required, the algorithm considers the set of elements that could be removed and later re-inserted. The slice nums[:k - 1] represents exactly those candidates, and the built-in max function efficiently determines the greatest among them. This value, stored in high, is a potential top after the allowed sequence of moves.

Compare with the element at position k when it exists

if k < size and nums[k] > high:
    return nums[k]

If the index k lies within the bounds of the list, the element nums[k] would become the top after removing the first k elements without any re-insertion. The algorithm checks whether this element exceeds the previously computed high. When it does, returning nums[k] yields a better result than any configuration that involves re-inserting a previously removed element.

Return the best achievable top from the removed set

return high

If the condition above is not satisfied, the optimal top is the maximum value among the removable subset, represented by high. This final return concludes the computation.

Edge Cases Addressed

The code explicitly covers several boundary conditions. When the input list has a length of one, the parity check (k & 1) determines whether the stack ends up empty. The early return for k <= 1 correctly handles the situation where no removal or a single removal is required, directly indexing into the list without risking an out-of-range error. The slice used for max is safe because the preceding condition guarantees that k is at least two, ensuring the slice contains at least one element. The comparison k < size prevents an index error when the k-th element does not exist, thereby handling cases where k exceeds the number of available elements.

Performance Optimizations

The implementation leverages early exits to avoid unnecessary work. By checking the single-element case and the small-k case first, the function can return immediately without performing any slicing or maximum computation. The use of Python’s built-in max on a slice provides a highly optimized traversal of the relevant portion of the list, benefiting from C-level loops under the hood. Additionally, the conditional k < size guards the second comparison, ensuring that the potentially expensive indexing operation is only performed when it is guaranteed to be valid. These design choices keep the runtime focused on the minimal amount of work required for each distinct scenario.

Imagine you have a tall stack of colorful toy blocks. Each block has a number written on it to show how special it is. You have a handful of turns to play a game with these blocks. In each turn, you can take the top block off the stack, or you can put a block back on. Because you only have a certain number of turns, you want to pick the very best block to keep at the top when you are done.

Sometimes, if you only have one block in the stack and you have to move, you might end up with an empty pile because you had to take the only one away. When you look at the stack, you first check how many blocks there are. If the stack is tiny with only one block, you might not be able to leave anything behind.

If you have a few turns to take blocks off, you look at all the blocks you are allowed to touch. You keep track of the biggest number you find while you are picking them up. While you are playing, you might see a new block that was hidden underneath the others. If that new block has a bigger number than any of the ones you already looked at, that becomes your new favorite. By the time you run out of turns, the number you saved is the winner.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java	Python			TS
	WalkCCC	C++		Java	Python
	leetcode.ca	C++		Java	Python		Go
	Progiez	C++		Java	Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	lkwq007				Python
	suxrobGM					C#
	varunu28			Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
varunu28	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality