2202. Maximize the Topmost Element After K Moves LeetCode Solution
In this guide, you will get 2202. Maximize the Topmost Element After K Moves LeetCode Solution with the best time and space complexity. The solution to Maximize the Topmost Element After K Moves problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximize the Topmost Element After K Moves
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.
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
Complexity Analysis
Time Complexity: O(\min(n, k))
Space Complexity: O(1)
2202. Maximize the Topmost Element After K Moves LeetCode Solution in C++
class Solution {
public:
int maximumTop(vector<int>& nums, int k) {
const int n = nums.size();
// After taking k elements, if there's something left, then return nums[k].
// Otherwise, return -1.
if (k == 0 || k == 1)
return n == k ? -1 : nums[k];
// Remove then add even number of times.
if (n == 1)
return k % 2 == 0 ? nums[0] : -1;
// Take min(n, k - 1) elements and put the largest one back.
const int mx = *max_element(nums.begin(), nums.begin() + min(n, k - 1));
if (k >= n)
return mx;
return max(mx, nums[k]);
}
}; /* code provided by PROGIEZ */
2202. Maximize the Topmost Element After K Moves LeetCode Solution in Java
class Solution {
public int maximumTop(int[] nums, int k) {
final int n = nums.length;
// After taking k elements, if there's something left, then return nums[k].
// Otherwise, return -1>
if (k == 0 || k == 1)
return n == k ? -1 : nums[k];
// Remove then add even number of times.
if (n == 1)
return k % 2 == 0 ? nums[0] : -1;
// Take min(n, k - 1) elements and put the largest one back.
final int mx = firstKMax(nums, k - 1);
if (k >= n)
return mx;
return Math.max(mx, nums[k]);
}
private int firstKMax(int[] nums, int k) {
int mx = 0;
for (int i = 0; i < nums.length && i < k; ++i)
mx = Math.max(mx, nums[i]);
return mx;
}
} // code provided by PROGIEZ
2202. Maximize the Topmost Element After K Moves LeetCode Solution in Python
class Solution:
def maximumTop(self, nums: list[int], k: int) -> int:
n = len(nums)
# After taking k elements, if we're left something, then we return nums[k]
# Otherwise, return -1.
if k == 0 or k == 1:
return -1 if n == k else nums[k]
# Remove then add even number of times.
if n == 1:
return -1 if k & 1 else nums[0]
# Take min(n, k - 1) elements and put the largest one back.
mx = max(nums[:min(n, k - 1)])
if k >= n:
return mx
return max(mx, nums[k]) # code by PROGIEZ
