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 there's something left, then return nums[k].
    // Otherwise, return -1.
    if (k == 0 || k == 1)
      return n == k ? -1 : nums[k];
    // Remove then add even number of times.
    if (n == 1)
      return k % 2 == 0 ? nums[0] : -1;
    // Take min(n, k - 1) elements and put the largest one back.
    const int mx = *max_element(nums.begin(), nums.begin() + min(n, k - 1));
    if (k >= n)
      return mx;
    return max(mx, 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
24
class Solution {
  public int maximumTop(int[] nums, int k) {
    final int n = nums.length;
    // After taking k elements, if there's something left, then return nums[k].
    // Otherwise, return -1>
    if (k == 0 || k == 1)
      return n == k ? -1 : nums[k];
    // Remove then add even number of times.
    if (n == 1)
      return k % 2 == 0 ? nums[0] : -1;
    // Take min(n, k - 1) elements and put the largest one back.
    final int mx = firstKMax(nums, k - 1);
    if (k >= n)
      return mx;
    return Math.max(mx, nums[k]);
  }

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

 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 number of times.
    if n == 1:
      return -1 if k & 1 else nums[0]
    # Take min(n, k - 1) elements and put the largest one back.
    mx = max(nums[:min(n, k - 1)])
    if k >= n:
      return mx
    return max(mx, nums[k])