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:
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 <= 109To solve the problem of maximizing the topmost element of the pile after k moves, we can use the following strategy:
Given that all k moves have to be utilized, maximize the topmost element using the first k elements of the array. If an element needs to be added back onto the pile, ensure it is the largest possible element already removed within the first k-1 elements.
If you are allowed exactly k moves, it is possible to look at the first k elements of the list to determine the maximum achievable topmost value after all moves are performed. Evaluate these scenarios:
This C solution iterates over the first min(k, numsSize-1) elements to find the maximum value that can be the topmost after k operations. If k is less than numsSize, it additionally checks if the k-th element is larger than the current maximum.
C++
Java
Python
C#
JavaScript
Time Complexity: O(min(k, n)), where n is the size of the array.
Space Complexity: O(1), as no additional storage is used except for variables.
In this approach, we optimize by considering the edge scenarios directly. Here are some of the strategies:
This approach is valuable for constraints management, yielding an alternative angle aside from fixed limits on initial segment exploration.
This C program extends the view range based on k and validates using boundary checks. It accommodates both continuation and remnant strategies, checking from the start up to index k to ensure maximum possibility is reflected in the outcome.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) in worse case if k is significantly large, closing loop early otherwise.
Space Complexity: O(1). Minimal in-place computation is observed.
| Approach | Complexity |
|---|---|
| Maximize Topmost Using First k Elements | Time Complexity: O(min(k, n)), where n is the size of the array. |
| Utilizing Continuity by Checking Boundaries | Time Complexity: O(n) in worse case if k is significantly large, closing loop early otherwise. |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,224 views views
Watch 9 more video solutions →Practice Maximize the Topmost Element After K Moves with our built-in code editor and test cases.
Practice on FleetCode