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 themaximum 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.

Examples

Example 1

1
2
3
4
5
6
7
8
9

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

1
2
3
4
5

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^5
  • 0 <= nums[i], k <= 10^9

Solution

Method 1 – Greedy Simulation by Case Analysis

Intuition

To maximize the topmost element after exactly k moves, we can remove up to k elements and add back any previously removed element. The answer depends on the value of k relative to the array length. We must consider all possible cases to maximize the topmost element.

Approach

  1. If k == 0, return the top element if the pile is not empty, else -1.
  2. If k == 1, the only option is to remove the top, so return the second element if it exists, else -1.
  3. If k < n, the answer is the maximum among the first k-1 elements and the kth element (if it exists).
  4. If k == n, the answer is the maximum among the first k-1 elements.
  5. If k > n, we can always add back any removed element, so the answer is the maximum in the array.
  6. If the pile is empty after k moves, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int maximumTop(vector<int>& nums, int k) {
        int n = nums.size();
        if (n == 0) return -1;
        if (k == 0) return n > 0 ? nums[0] : -1;
        if (k == 1) return n >= 2 ? nums[1] : -1;
        if (n == 1 && k % 2 == 1) return -1;
        int ans = 0;
        for (int i = 0; i < min(n, k-1); ++i) ans = max(ans, nums[i]);
        if (k < n) ans = max(ans, nums[k]);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func maximumTop(nums []int, k int) int {
    n := len(nums)
    if n == 0 { return -1 }
    if k == 0 { return nums[0] }
    if k == 1 { if n >= 2 { return nums[1] } else { return -1 } }
    if n == 1 && k%2 == 1 { return -1 }
    ans := 0
    for i := 0; i < min(n, k-1); i++ {
        if nums[i] > ans { ans = nums[i] }
    }
    if k < n && nums[k] > ans { ans = nums[k] }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int maximumTop(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) return -1;
        if (k == 0) return nums[0];
        if (k == 1) return n >= 2 ? nums[1] : -1;
        if (n == 1 && k % 2 == 1) return -1;
        int ans = 0;
        for (int i = 0; i < Math.min(n, k-1); i++) ans = Math.max(ans, nums[i]);
        if (k < n) ans = Math.max(ans, nums[k]);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun maximumTop(nums: IntArray, k: Int): Int {
        val n = nums.size
        if (n == 0) return -1
        if (k == 0) return nums[0]
        if (k == 1) return if (n >= 2) nums[1] else -1
        if (n == 1 && k % 2 == 1) return -1
        var ans = 0
        for (i in 0 until minOf(n, k-1)) ans = maxOf(ans, nums[i])
        if (k < n) ans = maxOf(ans, nums[k])
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def maximumTop(self, nums: list[int], k: int) -> int:
        n = len(nums)
        if n == 0:
            return -1
        if k == 0:
            return nums[0]
        if k == 1:
            return nums[1] if n >= 2 else -1
        if n == 1 and k % 2 == 1:
            return -1
        ans = max(nums[:min(n, k-1)]) if k > 1 else float('-inf')
        if k < n:
            ans = max(ans, nums[k])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn maximum_top(nums: Vec<i32>, k: i32) -> i32 {
        let n = nums.len() as i32;
        if n == 0 { return -1; }
        if k == 0 { return nums[0]; }
        if k == 1 { return if n >= 2 { nums[1] } else { -1 } };
        if n == 1 && k % 2 == 1 { return -1; }
        let mut ans = 0;
        for i in 0..std::cmp::min(n, k-1) {
            ans = ans.max(nums[i as usize]);
        }
        if k < n { ans = ans.max(nums[k as usize]); }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    maximumTop(nums: number[], k: number): number {
        const n = nums.length;
        if (n === 0) return -1;
        if (k === 0) return nums[0];
        if (k === 1) return n >= 2 ? nums[1] : -1;
        if (n === 1 && k % 2 === 1) return -1;
        let ans = 0;
        for (let i = 0; i < Math.min(n, k-1); i++) ans = Math.max(ans, nums[i]);
        if (k < n) ans = Math.max(ans, nums[k]);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(k) — for scanning up to the first k elements.
  • 🧺 Space complexity: O(1) — only a few variables are used.