Skip to main content
Talentd

Maximize the Topmost Element After K Moves - Solution & Explanation

MediumArrayGreedy21 min readAsked at: American Express
Practice this problem

Problem Statement

You are given a 0-indexed integer array nums representing the contents of a pile, where nums[0] is the topmost element of the pile.

In one move, you can perform either of the following:

  • If the pile is not empty, remove the topmost element of the pile.
  • If there are one or more removed elements, add any one of them back onto the pile. This element becomes the new topmost element.

You are also given an integer k, which denotes the total number of moves to be made.

Return the maximum value of the topmost element of the pile possible after exactly k moves. In case it is not possible to obtain a non-empty pile after k moves, return -1.

 

Example 1:

Input: nums = [5,2,2,4,0,6], k = 4
Output: 5
Explanation:
One of the ways we can end with 5 at the top of the pile after 4 moves is as follows:
- Step 1: Remove the topmost element = 5. The pile becomes [2,2,4,0,6].
- Step 2: Remove the topmost element = 2. The pile becomes [2,4,0,6].
- Step 3: Remove the topmost element = 2. The pile becomes [4,0,6].
- Step 4: Add 5 back onto the pile. The pile becomes [5,4,0,6].
Note that this is not the only way to end with 5 at the top of the pile. It can be shown that 5 is the largest answer possible after 4 moves.

Example 2:

Input: nums = [2], k = 1
Output: -1
Explanation: 
In the first move, our only option is to pop the topmost element of the pile.
Since it is not possible to obtain a non-empty pile after one move, we return -1.

 

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i], k <= 109

Approach Overview

Problem Overview: You are given an array where index 0 represents the top of a stack. In one move, you can either remove the top element or add back one of the previously removed elements. After exactly k moves, return the maximum possible value that can appear on the top of the stack. If it is impossible, return -1.

Approach 1: Maximize Topmost Using First k Elements (Greedy Scan) (Time: O(n), Space: O(1))

The key observation: during the first k-1 moves, you can freely remove elements. Any of those removed elements can be pushed back on the final move. That means the best candidate for the final top is the maximum element among the first k-1 elements removed. Additionally, if k < n, you could simply remove the first k elements and expose nums[k] as the new top. The final answer is the maximum between the largest value in nums[0..k-2] and nums[k] (when valid). Edge cases matter: if k == 0, the stack stays unchanged; if the array has one element and k is odd, every removal leaves the stack empty so the result is -1. This greedy scan works because the order of removed elements only matters for the last push operation.

Approach 2: Utilizing Continuity by Checking Boundaries (Greedy with Case Analysis) (Time: O(n), Space: O(1))

This approach analyzes the stack behavior across move boundaries instead of directly scanning candidates. Consider how the stack evolves after exactly k operations. If you remove fewer than k elements, you must push something back. If you remove exactly k elements, the element originally at index k becomes the top. By checking these boundary cases, you evaluate two possibilities: restoring the largest removed element or exposing the next untouched element in the array. Implementation iterates through at most the first k-1 elements to track the maximum removable candidate, then compares it against nums[k] when the array length allows. This framing helps reason about edge cases like k == 1, k > n, or a single-element stack.

Both approaches rely on simple iteration over an array and apply a greedy decision: always choose the largest value that can legally appear on top after exactly k operations. The trick is recognizing that the sequence of intermediate pushes does not matter—only the set of elements accessible before the final move.

Recommended for interviews: The greedy scan over the first k positions is the expected solution. Interviewers want to see you reason about operation constraints and reduce the problem to choosing the best candidate among reachable elements. Brute reasoning about stack simulations shows understanding, but identifying the greedy boundary conditions demonstrates stronger problem-solving skill.

Approach 1: Maximize Topmost Using First k Elements

To solve the problem of maximizing the topmost element of the pile after k moves, we can use the following strategy:

Given that all k moves have to be utilized, maximize the topmost element using the first k elements of the array. If an element needs to be added back onto the pile, ensure it is the largest possible element already removed within the first k-1 elements.

If you are allowed exactly k moves, it is possible to look at the first k elements of the list to determine the maximum achievable topmost value after all moves are performed. Evaluate these scenarios:

  • If k = 0, the top stays as is since no operations are allowed.
  • If k is 1 and only one element exists, it is impossible to have an element at the top after a move.
  • If k and nums.length are the same and k is even, you can remove all and re-add freely.
  • Otherwise, find the maximum of the first k elements if k is less than the size of the array, or the maximum in the entire list if allowed by operations.

This C solution iterates over the first min(k, numsSize-1) elements to find the maximum value that can be the topmost after k operations. If k is less than numsSize, it additionally checks if the k-th element is larger than the current maximum.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(min(k, n)), where n is the size of the array.
Space Complexity: O(1), as no additional storage is used except for variables.

Try this approach in the editor →

Approach 2: Utilizing Continuity by Checking Boundaries

In this approach, we optimize by considering the edge scenarios directly. Here are some of the strategies:

  • If k is less than the size of the array, observe the first k-1 elements to enable popping k times; however, when including continuity from operations, you can take the max of these and the kth element.
  • If k is equal to the size of the array, it reduces to determining the largest within the remanent as viewed normally but accounting for total removals allowed.
  • If k > n and it is even, every element can be cycled—so check the entire array for max, conversely cycle k-1 cases when k is odd.

This approach is valuable for constraints management, yielding an alternative angle aside from fixed limits on initial segment exploration.

This C program extends the view range based on k and validates using boundary checks. It accommodates both continuation and remnant strategies, checking from the start up to index k to ensure maximum possibility is reflected in the outcome.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) in worse case if k is significantly large, closing loop early otherwise.
Space Complexity: O(1). Minimal in-place computation is observed.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Maximize Topmost Using First k Elements

Time Complexity: O(min(k, n)), where n is the size of the array.
Space Complexity: O(1), as no additional storage is used except for variables.

Utilizing Continuity by Checking Boundaries

Time Complexity: O(n) in worse case if k is significantly large, closing loop early otherwise.
Space Complexity: O(1). Minimal in-place computation is observed.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Maximize Topmost Using First k ElementsO(n)O(1)General case. Direct greedy scan of the first k reachable elements.
Utilizing Continuity by Checking BoundariesO(n)O(1)Useful for reasoning through edge cases like k=1, k>n, or single-element arrays.

Video Solution

2202. Maximize the Topmost Element After K Moves || Leetcode Weekly Contest 284 || Leetcode 2202 • Bro Coders • 2,118 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximize the Topmost Element After K Moves easy or hard?
The problem is rated Medium on LeetCode because the implementation is short but the edge cases are tricky. Correctly handling k == 0, k == 1, k > n, and single-element arrays is the main challenge.
Maximize the Topmost Element After K Moves Python/Java solution
The standard implementation iterates through the first k-1 elements to compute the maximum removable value, then compares it with nums[k] if that index exists. The same greedy logic works in Python, Java, C++, and other languages with O(n) time and constant extra space.
How to solve Maximize the Topmost Element After K Moves in O(n)?
Iterate through the first k-1 elements and track the maximum value that could be removed and later pushed back. If k is less than the array length, also consider nums[k] as a candidate because removing exactly k elements exposes it. Return the maximum of these candidates while handling special cases like a single-element array with odd k.
What is the best approach for Maximize the Topmost Element After K Moves?
The optimal approach is a greedy scan over the first k reachable elements. Track the maximum among the first k-1 elements that could be removed and pushed back, and compare it with nums[k] if the array still has elements after k removals. This runs in O(n) time with O(1) extra space.
Is Maximize the Topmost Element After K Moves asked at Google/Amazon/Meta?
This problem represents the type of greedy reasoning and edge‑case analysis commonly asked at companies like Google, Amazon, and Meta. While the exact problem may vary, interview questions often test the ability to analyze stack-like operations and optimize using array scanning.
What data structure is used in Maximize the Topmost Element After K Moves?
The problem uses an array that behaves like a stack where index 0 represents the top element. The algorithm itself does not require additional data structures; it relies on greedy analysis and simple iteration through the array.
What is the time complexity of Maximize the Topmost Element After K Moves?
The optimal solution runs in O(n) time because you scan at most the first min(n, k) elements of the array to compute the best candidate. Space complexity is O(1) since only a few variables are used to track the maximum value and handle edge cases.

Ready to solve this problem?

Practice Maximize the Topmost Element After K Moves with our built-in code editor and test cases.

Practice on FleetCode
Previous

Gas Station