[LeetCode] Maximize the Topmost Element After K Moves

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:

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.

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.

Approach: We will be greedy here. First just filter out some obvious cases like 

• if  nums just one element then if k is odd then we won't have any element after k moves. We will have nums[0] at top only if k is even.
• If k is more than the length of the array nums then we can always have the maximum element of nums at the top.

Now we will see the case where 0 <= k <= length of nums. We can never get the kth element of nums i.e. nums[k - 1] at top in k moves. Right. See for yourself, we can remove k - 1 elements in k - 1 moves now at kth move either we can remove the kth element or put one of the removed elements at top. That means either one of the k - 1 removed elements will be on top or (k + 1)th element i.e. nums[k] will be on top. As we want to place the maximum possible one, we can say that after k moves, the maximum element we can place is:

MAX ( MAX(nums[0]...nums[k - 2]), nums[k])

That's all!

Implementation in C#:

    public int MaximumTop(int[] nums, int k)

    {

int length = nums?.Length ?? 0;

if (length == 0)

{

return -1;

}

if (length == 1)

{

if (k % 2 == 0)

{

return nums[0];

}

else

{

return -1;

}

}

if (k > length)

{

return nums.Max();

}

int max = -1;

for (int i = 0; i < k - 1; ++i)

{

max = Math.Max(max, nums[i]);

}

return k < length ? Math.Max(max, nums[k]) : max;

}

Complexity: O(n)