2202. Maximize Topmost Element After K Moves

The problem

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 <= 10⁵
0 <= nums[i], k <= 10⁹

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.

Python

def maxTop(nums, k):
    n = len(nums)
    if n == 1:
        return -1 if k % 2 == 1 else nums[0]

    max_val = max(nums[:min(k, n-1)])
    if k < n:
        max_val = max(max_val, nums[k])

    return max_val

nums = [5, 2, 2, 4, 0, 6]
k = 4
print(maxTop(nums, k))  # Outputs: 5

Java

import java.util.*;

public class MaxTop {
    public static int maxTop(int[] nums, int k) {
        int n = nums.length;
        if (n == 1) return (k % 2 == 1) ? -1 : nums[0];
        int result = Integer.MIN_VALUE;

        for (int i = 0; i < Math.min(k, n - 1); i++) {
            result = Math.max(result, nums[i]);
        }
        if (k < n) {
            result = Math.max(result, nums[k]);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {5, 2, 2, 4, 0, 6};
        int k = 4;
        System.out.println(maxTop(nums, k));  // Outputs: 5
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

int maxTop(std::vector<int>& nums, int k) {
    int n = nums.size();
    if (n == 1) return (k % 2 == 1) ? -1 : nums[0];
    int result = *std::max_element(nums.begin(), nums.begin() + std::min(k, n - 1));
    if (k < n) result = std::max(result, nums[k]);
    return result;
}

int main() {
    std::vector<int> nums = {5, 2, 2, 4, 0, 6};
    int k = 4;
    std::cout << maxTop(nums, k) << std::endl;  // Outputs: 5
    return 0;
}

JavaScript

function maxTop(nums, k) {
    const n = nums.length;
    if (n === 1) return (k % 2 === 1) ? -1 : nums[0];

    let maxVal = Math.max(...nums.slice(0, Math.min(k, n - 1)));
    if (k < n) {
        maxVal = Math.max(maxVal, nums[k]);
    }

    return maxVal;
}

const nums = [5, 2, 2, 4, 0, 6];
const k = 4;
console.log(maxTop(nums, k));  // Outputs: 5

#include <stdio.h>
#include <limits.h>

int maxTop(int* nums, int numsSize, int k) {
    if (numsSize == 1) return (k % 2 == 1) ? -1 : nums[0];
    int maxVal = INT_MIN;
    int limit = (k < numsSize) ? k : numsSize - 1;
    for (int i = 0; i < limit; ++i) {
        if (nums[i] > maxVal) {
            maxVal = nums[i];
        }
    }
    if (k < numsSize) {
        maxVal = (nums[k] > maxVal) ? nums[k] : maxVal;
    }
    return maxVal;
}

int main() {
    int nums[] = {5,2,2,4,0,6};
    int k = 4;
    printf("%d\n", maxTop(nums, sizeof(nums)/sizeof(nums[0]), k));  // Outputs: 5
    return 0;
}

using System;

public class Solution {
    public int MaxTop(int[] nums, int k) {
        int n = nums.Length;
        if (n == 1) return (k % 2 == 1) ? -1 : nums[0];
        int result = int.MinValue;

        for (int i = 0; i < Math.Min(k, n - 1); i++) {
            result = Math.Max(result, nums[i]);
        }
        if (k < n) {
            result = Math.Max(result, nums[k]);
        }

        return result;
    }

    static void Main() {
        int[] nums = {5, 2, 2, 4, 0, 6};
        int k = 4;
        Solution sol = new Solution();
        Console.WriteLine(sol.MaxTop(nums, k));  // Outputs: 5
    }
}

This Python function calculates the maximum value in the first min(k, n-1) segment and also compares this maximum to the k-th element if k is within bounds. It effectively finds the desired maximum topmost value in the array after the defined k operations.

Complexity

Time Complexity: O(min(k, n)), where n is the number of elements in nums.
Space Complexity: O(1), as only a small number of extra variables are used.

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.

Python

def maxTopUsingBoundaries(nums, k):
    n = len(nums)
    if n == 1: return -1 if k % 2 == 1 else nums[0]

    max_val = max(nums[:min(k + 1, n)])
    if k >= n:
        max_val = max(nums)

    return max_val

nums = [5, 2, 2, 4, 0, 6]
k = 4
print(maxTopUsingBoundaries(nums, k))  # Outputs: 5

Java

import java.util.*;

public class MaxTopBoundaries {
    public static int maxTopUsingBoundaries(int[] nums, int k) {
        int n = nums.length;
        if (n == 1) return (k % 2 == 1) ? -1 : nums[0];
        int result = Integer.MIN_VALUE;

        for (int i = 0; i <= Math.min(k, n); i++) {
            if (i < n && nums[i] > result) {
                result = nums[i];
            }
        }
        if (k >= n) {
            for (int num : nums) {
                if (num > result) result = num;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {5, 2, 2, 4, 0, 6};
        int k = 4;
        System.out.println(maxTopUsingBoundaries(nums, k));  // Outputs: 5
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

int maxTopUsingBoundaries(const std::vector<int>& nums, int k) {
    int n = nums.size();
    if (n == 1) return (k % 2 == 1) ? -1 : nums[0];
    int result = *std::max_element(nums.begin(), nums.begin() + std::min(n, (k + 1)));
    if (k > n) result = *std::max_element(nums.begin(), nums.end());
    return result;
}

int main() {
    std::vector<int> nums = {5, 2, 2, 4, 0, 6};
    int k = 4;
    std::cout << maxTopUsingBoundaries(nums, k) << std::endl;  // Outputs: 5
    return 0;
}

JavaScript

function maxTopUsingBoundaries(nums, k) {
    const n = nums.length;
    if (n === 1) return (k % 2 === 1) ? -1 : nums[0];

    let maxVal = Math.max(...nums.slice(0, Math.min(k + 1, n)));
    if (k >= n) {
        maxVal = Math.max(...nums);
    }

    return maxVal;
}

const nums = [5, 2, 2, 4, 0, 6];
const k = 4;
console.log(maxTopUsingBoundaries(nums, k));  // Outputs: 5

#include <stdio.h>
#include <limits.h>

int maxTopUsingBoundaries(int* nums, int numsSize, int k) {
    if (numsSize == 1) return (k % 2 == 1) ? -1 : nums[0];
    int maxVal = INT_MIN;
    for (int i = 0; i < numsSize && i <= k; ++i) {
        if (nums[i] > maxVal) {
            maxVal = nums[i];
        }
    }
    if (k > numsSize) maxVal = *max_element(nums, nums + numsSize);
    return maxVal;
}

int main() {
    int nums[] = {5,2,2,4,0,6};
    int k = 4;
    printf("%d\n", maxTopUsingBoundaries(nums, sizeof(nums)/sizeof(nums[0]), k));  // Outputs: 5
    return 0;
}

using System;

public class Solution {
    public int MaxTopUsingBoundaries(int[] nums, int k) {
        int n = nums.Length;
        if (n == 1) return (k % 2 == 1) ? -1 : nums[0];
        int maxVal = int.MinValue;

        for (int i = 0; i <= Math.Min(k, n); i++) {
            if (i < n && nums[i] > maxVal) {
                maxVal = nums[i];
            }
        }
        if (k >= n) {
            foreach (int num in nums) {
                if (num > maxVal) maxVal = num;
            }
        }

        return maxVal;
    }

    static void Main() {
        int[] nums = {5, 2, 2, 4, 0, 6};
        int k = 4;
        Solution sol = new Solution();
        Console.WriteLine(sol.MaxTopUsingBoundaries(nums, k));  // Outputs: 5
    }
}

The Python solution uses slicing for extended logic neatly, employing list characteristics and max determination naturally, converging operations ensuring true max capture subtly through programming language affordances.

Complexity

Time Complexity: O(n) as limit-wide iterate extends, yet concise with thresholds on real passing.
Space Complexity: O(1). With native handling of required structures.

Try this approach in the editor

Approach 3: Default Approach

func maximumTop(nums []int, k int) int {
	if k == 0 {
		return nums[0]
	}
	n := len(nums)
	if n == 1 {
		if k%2 == 1 {
			return -1
		}
		return nums[0]
	}
	ans := -1
	for i := 0; i < min(k-1, n); i++ {
		ans = max(ans, nums[i])
	}
	if k < n {
		ans = max(ans, nums[k])
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Maximize Topmost Using First k Elements	Time Complexity: O(min(k, n)), where n is the number of elements in nums. Space Complexity: O(1), as only a small number of extra variables are used.
Utilizing Continuity by Checking Boundaries	Time Complexity: O(n) as limit-wide iterate extends, yet concise with thresholds on real passing. Space Complexity: O(1). With native handling of required structures.
Default Approach	–

Complexity analysis

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.

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.

Maximize the Topmost Element After K Moves solution and explanation

The problem

Approach overview

Approach 1: Maximize Topmost Using First k Elements

Approach 2: Utilizing Continuity by Checking Boundaries

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximize the Topmost Element After K Moves solution and explanation

The problem

Approach overview

Approach 1: Maximize Topmost Using First k Elements

Approach 2: Utilizing Continuity by Checking Boundaries

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems