We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximize the Topmost Element After K Moves

Number: 1346

Difficulty: Medium

Paid? No

Companies: American Express

Problem Description

Given a pile represented as an array where the 0th element is the top, you are allowed exactly k moves. In each move you can either remove the top element (if the pile is not empty) or add back any previously removed element (which becomes the new top). The goal is to maximize the value of the top element after k moves. If it is impossible to have a non-empty pile after exactly k moves, return -1.

Key Insights

  • There are two types of operations: removal (pop) and pushing back one of the removed elements.
  • When k moves are made, some elements are “available” to be pushed back (the ones removed in earlier moves).
  • The answer depends on the relationship between k and the number of elements n in the array.
  • Special cases: when k == 0 the top remains unchanged, and when n == 1, care must be taken depending on whether k is odd or even.
  • For k less than n, the answer is the maximum between an element that is naturally exposed by removing k elements and the maximum among some of the removed ones.
  • For k greater than n, you can always eventually push back the maximum element found in the entire array.

Space and Time Complexity

Time Complexity: O(n) in the worst-case, since we may scan parts of the array. Space Complexity: O(1) extra space, aside from the input storage.

Solution

The solution leverages a greedy approach and careful analysis of the operations available with k moves:

  1. Handle k == 0 by returning the current top element.
  2. Handle the special case when there is only 1 element: if k is odd then after removals the pile will be empty, so return -1; otherwise, return that element.
  3. If k is less than the number of elements n:
    • For k == 1, the only valid move is to remove the top element, making the new top element nums[1].
    • For k >= 2, two choices are available: a. Remove k elements and then put back one of the removed ones. The best candidate from the removed ones comes from the first (k-1) elements. b. Remove (k-1) elements and then keep the kth element as the top.
    • The answer is the maximum of these two possibilities.
  4. If k equals n, you cannot have nums[k] because it would be out-of-bounds; thus, the answer is the maximum among the first (n-1) removed elements.
  5. If k is greater than n, you can always remove all elements and then push back the maximum element from the entire array.

Data structures used are arrays and simple variables. The algorithm works by scanning a portion or the whole array to find maximum values based on the moves available.

Code Solutions

# Python solution
def maximumTop(nums, k):
    n = len(nums)
    # If no moves, return the current top.
    if k == 0:
        return nums[0]
    # Special case: only one element.
    if n == 1:
        return -1 if k % 2 == 1 else nums[0]
    # When moves are less than the length of the array.
    if k < n:
        if k == 1:
            # Only one move, so the top becomes the second element.
            return nums[1]
        # For k>=2, the candidate values:
        # 1. Maximum of the first k-1 elements (available for push back).
        candidate1 = max(nums[:k-1])
        # 2. The kth element naturally becomes the top if we remove k-1 elements.
        candidate2 = nums[k]
        return max(candidate1, candidate2)
    # When k equals n, you cannot choose the kth element.
    if k == n:
        return max(nums[:k-1])
    # When k is greater than n, we can eventually bring back the maximum element.
    return max(nums)

# Example usage:
print(maximumTop([5,2,2,4,0,6], 4))  # Expected output: 5
← Back to All Questions