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:
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 <= 1050 <= nums[i], k <= 109Problem 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.
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:
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.
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.
In this approach, we optimize by considering the edge scenarios directly. Here are some of the strategies:
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.
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.
| Approach | Complexity |
|---|---|
| Maximize Topmost Using First k Elements | Time Complexity: O(min(k, n)), where n is the size of the array. |
| Utilizing Continuity by Checking Boundaries | Time Complexity: O(n) in worse case if k is significantly large, closing loop early otherwise. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Maximize Topmost Using First k Elements | O(n) | O(1) | General case. Direct greedy scan of the first k reachable elements. |
| Utilizing Continuity by Checking Boundaries | O(n) | O(1) | Useful for reasoning through edge cases like k=1, k>n, or single-element arrays. |
2202. Maximize the Topmost Element After K Moves || Leetcode Weekly Contest 284 || Leetcode 2202 • Bro Coders • 2,070 views views
Watch 9 more video solutions →Practice Maximize the Topmost Element After K Moves with our built-in code editor and test cases.
Practice on FleetCode