Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2202.html
2202. Maximize the Topmost Element After K Moves (Medium)
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 <= 1050 <= nums[i], k <= 109
Companies:
American Express
Related Topics:
Array
Similar Questions:
Solution 1.
See comments in the code.
A note on the removing min(k - 1, N) elements case:
What if k > N + 1 – there are still steps left after removing N elements and putting back the greatest one? We can always waste these steps by putting another element in and out. Since N >= 2 in this case, it’s guaranteed to have another element to waste steps.
-
// OJ: https://leetcode.com/problems/maximize-the-topmost-element-after-k-moves/ // Time: O(min(N, K)) // Space: O(1) class Solution { public: int maximumTop(vector<int>& A, int k) { int N = A.size(); if (k == 0) return N >= 1 ? A[0] : -1; // if no moves allowed, return the topmost element if any if (k == 1) return N == 1 ? -1 : A[1]; // if only one move is allowed, we can only remove the topmost element if (N == 1) return k % 2 == 0 ? A[0] : -1; // if `N == 1`, we can return the topmost element if `k` is a even number (keep removing the topmost element and adding it back). int mx = *max_element(begin(A), begin(A) + min(k - 1, N)); // we can take `min(k-1, N)` elements and put back the largest one on the top if (k < N) mx = max(mx, A[k]); // If `k < N`, we can take all the topmost `k` elements and return the one left at the top return mx; } }; -
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 ############ # 2202. Maximize the Topmost Element After K Moves # https://leetcode.com/problems/maximize-the-topmost-element-after-k-moves/ class Solution: def maximumTop(self, nums: List[int], k: int) -> int: n = len(nums) if k == 0: return nums[0] if k == 1: return -1 if n == 1 else nums[1] if n == 1: return -1 if k & 1 else nums[0] mmax = max(nums[:min(n, k - 1)]) if k < n: mmax = max(mmax, nums[k]) return mmax -
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; } } -
func maximumTop(nums []int, k int) int { if k == 0 { return nums[0] } n := len(nums) if n == 1 { if k%2 == 1 { return -1 } return nums[0] } ans := -1 for i := 0; i < min(k-1, n); i++ { ans = max(ans, nums[i]) } if k < n { ans = max(ans, nums[k]) } return ans } func max(a, b int) int { if a > b { return a } return b } func min(a, b int) int { if a < b { return a } return b }
Discuss
https://leetcode.com/problems/maximize-the-topmost-element-after-k-moves/discuss/1844102/