Maximize the Topmost Element After K Moves

Maximize the Topmost Element After K Moves - Problem

Array Greedy 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [5,2,7,4,1], k = 2

› Output: 7

💡 Note: We can remove 5 and 2 (2 moves), making 7 the topmost element. Or remove 5, then add it back, then remove it and 2 to get 7 on top.

Example 2 — All Elements Removed

$ Input: nums = [2], k = 1

› Output: -1

💡 Note: With only 1 element and 1 move, we must remove it, leaving an empty pile.

Example 3 — Return to Original

$ Input: nums = [73,98,39,51], k = 4

› Output: 98

💡 Note: We can remove all 4 elements, then add back the maximum (98) to make it topmost.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ k ≤ 2 × 10⁹
1 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array [5,2,7,4,1] with k=2 moves

Process

Remove elements to reach better ones or rearrange

Output

Maximum possible top element: 7

Key Takeaway

🎯 Key Insight: Analyze which positions are reachable with exactly k moves, considering both removal and addition operations

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Meta 12

The key insight is to analyze which elements are reachable with exactly k moves. We can remove up to k elements and potentially add them back. The optimal strategy depends on whether k allows us to access better elements deeper in the pile or return to previously removed ones. Best approach uses greedy analysis: Time O(n), Space O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(2^k)	O(k)	Try all possible sequences of moves using backtracking
Greedy Strategy Analysis	O(n)	O(1)	Analyze reachable elements and choose optimal strategy based on move constraints

Brute Force Simulation — Algorithm Steps

Step 1: Use backtracking to explore all move sequences
Step 2: For each state, try removing top element or adding back removed elements
Step 3: Track maximum topmost value when exactly k moves are used

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Start with pile and k moves

Branch

Try remove or add operations

Result

Return maximum across all paths

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int backtrack(int* pile, int pileSize, int* removed, int removedSize, int movesLeft) {
    if (movesLeft == 0) {
        return pileSize == 0 ? -1 : pile[0];
    }
    
    int maxVal = -1;
    
    // Option 1: Remove top element
    if (pileSize > 0) {
        int top = pile[0];
        for (int i = 0; i < pileSize - 1; i++) {
            pile[i] = pile[i + 1];
        }
        removed[removedSize] = top;
        int val = backtrack(pile, pileSize - 1, removed, removedSize + 1, movesLeft - 1);
        if (val > maxVal) maxVal = val;
        for (int i = pileSize - 1; i > 0; i--) {
            pile[i] = pile[i - 1];
        }
        pile[0] = top;
    }
    
    return maxVal;
}

int solution(int* nums, int numsSize, int k) {
    int* pile = (int*)malloc(numsSize * sizeof(int));
    int* removed = (int*)malloc(numsSize * sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        pile[i] = nums[i];
    }
    int result = backtrack(pile, numsSize, removed, 0, k);
    free(pile);
    free(removed);
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[100];
    int numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(nums, numsSize, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^k)

Each move has up to 2 choices (remove or add), creating exponential branching

✓ Linear Growth

Space Complexity

O(k)

Recursion stack depth is k, plus storage for removed elements

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

487 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler