# Maximize the Topmost Element After K Moves
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximize-the-topmost-element-after-k-moves)
Canonical: https://scaleengineer.com/dsa/problems/maximize-the-topmost-element-after-k-moves
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [American Express](https://scaleengineer.com/companies/american-express)
---
## 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 <= 105`
* `0 <= nums[i], k <= 109`

# Approaches
## Brute-Force Backtracking
This approach explores all possible sequences of `k` moves using recursion or backtracking. We define a function that takes the current state of the pile, the set of removed elements, and the number of moves remaining. In each step, we explore two branches: removing the top element (if the pile is not empty) and adding a previously removed element back to the top (if any exist). We keep track of the maximum top element found after exactly `k` moves. This method is presented for conceptual understanding and is not a practical solution.
**Time:** O(n^k), where `n` is the number of elements and `k` is the number of moves. At each of the `k` steps, we could have up to `n` choices for which element to add back, leading to an exponential number of paths. · **Space:** O(k * n), where `k` is the number of moves and `n` is the number of elements. This is for the recursion stack, where at each level we might need to store the state of the pile and the set of removed elements.
**Pros:** Conceptually simple to understand as it directly models the problem statement.; Guaranteed to find the correct answer by exploring the entire search space.
**Cons:** Extremely inefficient due to its exponential time complexity, making it infeasible for the given constraints.; High space complexity from the recursion depth and the need to store copies of the pile state.
### Explanation
The brute-force strategy involves a recursive exploration of every possible move at each step. We can define a function, say `findMax(k, pile, removed_elements)`, that represents the state of the problem.

The base case for the recursion is when `k` (moves remaining) becomes 0. At this point, if the pile is not empty, we have a potential answer, which is the top element. If the pile is empty, this path is invalid.

In the recursive step (when `k > 0`), we branch out based on the allowed moves:
1.  **Remove operation**: If the pile is not empty, we simulate removing the top element. We then make a recursive call with `k-1` moves, the updated pile, and the newly removed element added to our set of removed elements.
2.  **Add operation**: If there are any removed elements, we can add any one of them back. We iterate through each removed element, simulate adding it to the top of the pile, and make a recursive call with `k-1` moves.

The function returns the maximum value obtained from all valid terminal states.

Due to the massive state space (`(pile_state, removed_elements_state, k)`) and the branching factor, this approach is computationally prohibitive.

```java
// This is a conceptual representation. A real implementation would be too slow
// and complex for the given constraints, likely causing a Time Limit Exceeded error.
class Solution {
    public int maximumTop(int[] nums, int k) {
        // The state space is too large for a direct recursive solution.
        // The number of branches at each step can be up to nums.length.
        // The depth of recursion is k.
        // This leads to a complexity roughly O((n)^k), which is not feasible.
        // A practical implementation would require memoization with a complex state,
        // but the state space itself is too large.
        return -1; // Placeholder for this infeasible approach.
    }
}
```
### Algorithm
*   Define a recursive function `solve(moves_left, current_pile, removed_elements)`.
*   **Base Case:** If `moves_left == 0`:
    *   If `current_pile` is empty, return -1.
    *   Otherwise, return the top element of `current_pile`.
*   Initialize `max_top = -1`.
*   **Recursive Step 1 (Remove):**
    *   If `current_pile` is not empty:
        *   Simulate removing the top element `x`.
        *   Update `max_top = max(max_top, solve(moves_left - 1, new_pile, removed_elements + {x}))`.
*   **Recursive Step 2 (Add):**
    *   For each element `y` in `removed_elements`:
        *   Simulate adding `y` to the top of the pile.
        *   Update `max_top = max(max_top, solve(moves_left - 1, new_pile_with_y, removed_elements))`.
*   Return `max_top`.

## Single Pass Greedy Analysis
This efficient approach avoids simulating every move by analyzing the possible final states. The topmost element after `k` moves must either be an element that was never removed (specifically `nums[k]`) or an element that was removed and then added back (one of `nums[0]...nums[k-2]`). By identifying the candidates from these two scenarios and handling edge cases, we can determine the maximum possible value in a single pass over a small portion of the input array.
**Time:** O(min(n, k)), where `n` is `nums.length`. The loop runs at most `k-1` times or `n` times, whichever is smaller. · **Space:** O(1), as we only use a few variables to keep track of the maximum value and loop indices.
**Pros:** Highly efficient with a time complexity linear in `k` or `n`.; Requires only constant extra space.; Simple to implement once the logic is understood.
**Cons:** The logic is not immediately obvious and requires careful case analysis to be convinced of its correctness.
### Explanation
Instead of exploring all move sequences, we can deduce the possible candidates for the maximum top element. We must first handle a key edge case:

*   If `nums.length == 1`: With a single element, we can only alternate between removing it and adding it back. If `k` is odd, the pile will end up empty, so we return -1. If `k` is even, the pile will end up with `nums[0]` on top.

For the general case, we identify two main scenarios for the final top element:

1.  **The top element is one of the first `k-1` elements**: We can use `k-1` moves to remove some number of elements from the top. With the final `k`-th move, we can add any of the removed elements back. To get the maximum value, we would choose to add back the largest element among those removed. The largest possible pool of removed elements we can choose from are `nums[0], ..., nums[k-2]`. So, the maximum of these elements is a candidate for the answer. This covers cases where `k > n` as well; if we remove all `n` elements, we can add back the maximum of the entire array.

2.  **The top element is `nums[k]`**: This can be achieved by simply performing `k` consecutive removal operations. This is only possible if the pile has at least `k+1` elements, i.e., `k < nums.length`.

By finding the maximum of all candidates from these two scenarios, we arrive at the answer. The algorithm iterates up to `min(n, k-1)` to find the first type of candidate and then checks `nums[k]` for the second type.

```java
class Solution {
    public int maximumTop(int[] nums, int k) {
        int n = nums.length;

        // If k is 0, no moves are made. The top is nums[0].
        if (k == 0) {
            return n > 0 ? nums[0] : -1;
        }

        // If there's only one element, the pile is non-empty after k moves only if k is even.
        if (n == 1) {
            return (k % 2 == 1) ? -1 : nums[0];
        }

        int maxVal = 0;
        // Candidate 1: Max of the first k-1 elements.
        // We can remove these and use the last move to add the max one back.
        // We can access at most n elements or k-1 elements.
        int limit = Math.min(n, k - 1);
        for (int i = 0; i < limit; i++) {
            maxVal = Math.max(maxVal, nums[i]);
        }

        // Candidate 2: The element at index k after k removals.
        // This is only possible if k is less than the number of elements.
        if (k < n) {
            maxVal = Math.max(maxVal, nums[k]);
        }

        return maxVal;
    }
}
```
### Algorithm
*   Let `n` be the length of `nums`.
*   Handle the edge case where the pile has only one element (`n == 1`). If `k` is odd, it's impossible to have a non-empty pile, so return -1. If `k` is even, we can remove and add the element back, so return `nums[0]`.
*   Initialize a variable `max_candidate` to 0 (or a suitable minimum).
*   **Candidate Set 1:** Consider elements that are removed and then added back. To do this, we can use `k-1` moves to manipulate the pile and the last move to add an element. The pool of elements we can add back are the ones we removed. To maximize our chances, we should consider the maximum among the first `k-1` elements. We iterate from `i = 0` to `min(n, k - 1) - 1` and update `max_candidate` with `nums[i]` if it's larger.
*   **Candidate Set 2:** Consider the element that is left on top after exactly `k` removals. This would be `nums[k]`. This is a valid candidate only if the pile is large enough, i.e., `k < n`. If so, we update `max_candidate = max(max_candidate, nums[k])`.
*   The final answer is the `max_candidate` found.

# Solutions
### Java

```java
class Solution {
public
  int maximumTop(int[] nums, int k) {
    if (k == 0) {
      return nums[0];
    }
    int n = nums.length;
    if (n == 1) {
      if (k % 2 == 1) {
        return -1;
      }
      return nums[0];
    }
    int ans = -1;
    for (int i = 0; i < Math.min(k - 1, n); ++i) {
      ans = Math.max(ans, nums[i]);
    }
    if (k < n) {
      ans = Math.max(ans, nums[k]);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximumTop(vector<int> &nums, int k) {
    if (k == 0)
      return nums[0];
    int n = nums.size();
    if (n == 1) {
      if (k % 2)
        return -1;
      return nums[0];
    }
    int ans = -1;
    for (int i = 0; i < min(k - 1, n); ++i)
      ans = max(ans, nums[i]);
    if (k < n)
      ans = max(ans, nums[k]);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maximumTop(self, nums: List[int], k: int) -> int: if k == 0: return nums[0] n = len(nums) if n == 1: if k % 2: return - 1 return nums[0] ans = max(nums[: k - 1], default=- 1) if k < n: ans = max(ans, nums[k]) return ans

```