Skip to content

2202. Maximize the Topmost Element After K Moves

  • Time: $O(\min(n, k))$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  int maximumTop(vector<int>& nums, int k) {
    const int n = nums.size();
    // After taking k elements, if we're left something, then we return nums[k];
    // Otherwise return -1
    if (k == 0 || k == 1)
      return n == k ? -1 : nums[k];
    // (remove then add) even times
    if (n == 1)
      return k & 1 ? -1 : nums[0];
    // Take min(n, k - 1) elements and put back the largest one
    const int max = *max_element(nums.begin(), nums.begin() + min(n, k - 1));
    if (k >= n)
      return max;
    return std::max(max, nums[k]);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int maximumTop(int[] nums, int k) {
    final int n = nums.length;
    // After taking k elements, if we're left something, then we return nums[k]; otherwise return -1
    if (k == 0 || k == 1)
      return n == k ? -1 : nums[k];
    // (remove then add) even times
    if (n == 1)
      return k % 2 == 0 ? nums[0] : -1;
    // Take min(n, k - 1) elements and put back the largest one
    final int max = firstKMax(nums, k - 1);
    if (k >= n)
      return max;
    return Math.max(max, nums[k]);
  }

  private int firstKMax(int[] nums, int k) {
    int max = 0;
    for (int i = 0; i < nums.length && i < k; ++i)
      max = Math.max(max, nums[i]);
    return max;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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 times
    if n == 1:
      return -1 if k & 1 else nums[0]
    # Take min(n, k - 1) elements and put back the largest one
    maxi = max(nums[:min(n, k - 1)])
    if k >= n:
      return maxi
    return max(maxi, nums[k])