Maximize the Topmost Element After K Moves

medium array greedy

Problem

You are given a 0-indexed array nums that represents a pile, where index 0 is the topmost element. You are also given an integer k. You must make exactly k moves. On each move you either remove the current topmost element, or add back to the top one element you removed on an earlier move. Return the largest value that can be sitting on top after exactly k moves, or -1 if no element can be on top.

Inputnums = [5, 2, 2, 4, 0, 6], k = 4

Output5

Remove the first 3 elements (5, 2, 2), then on the 4th move add 5 back to the top. The best reachable values are the largest of nums[0..k-2] = max(5, 2, 2) = 5, versus nums[k] = nums[4] = 0; the winner is 5.

nums (comma-separated)

def maximum_top(nums, k):
    n = len(nums)
    if n == 1:
        return -1 if k % 2 == 1 else nums[0]
    best = -1
    for i in range(min(k - 1, n)):
        best = max(best, nums[i])
    if k < n:
        best = max(best, nums[k])
    return best

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

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

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

Explanation

Every move is one of two things: pop the current top, or push back something you popped earlier. Think about which original element can end up on top after exactly k moves, then take the maximum over all reachable elements.

Spend every move removing. If you remove k times in a row (and that is possible, i.e. k < n), then nums[k] — the element originally at index k — is left exposed on top. So nums[k] is always a candidate when k < n.

Remove a few, then add the best one back. Suppose you pop the first k − 1 elements (any of nums[0..k-2]), and use the very last, k-th move to push your favorite removed element back on top. That favorite can be the maximum of nums[0 .. k-2]. This needs at least 2 moves (one remove, one add), so it only applies when k ≥ 2, and you can only reach indices up to min(k-1, n).

Putting it together, the answer is the larger of those two candidates: max( max(nums[0 .. k-2]), nums[k] ), where the second term is dropped when k ≥ n. You never need to consider anything else — popping then re-adding cannot reach an index beyond k − 2, and a straight run of pops can only expose nums[k].

The tiny edge case. If the pile has only one element (n == 1), you cannot leave anything on top after an odd number of moves: one move removes the only element, and there is nothing else to swap with, so it just toggles between “present” and “empty”. With an even k you can remove it and add it back, ending with nums[0]; with an odd k the pile ends empty, so the answer is -1.

Default example nums = [5, 2, 2, 4, 0, 6], k = 4: the add-back candidate is max(nums[0..2]) = max(5, 2, 2) = 5, and the straight-pop candidate is nums[4] = 0. The maximum is 5.

A single scan over at most k indices does all the work, so the time is linear and no extra memory is needed.

Time: O(min(k, n)) Space: O(1)