Welcome to Subscribe On Youtube

3828. Final Element After Subarray Deletions

Description

You are given an integer array nums.

Two players, Alice and Bob, play a game in turns, with Alice playing first.

  • In each turn, the current player chooses any subarray nums[l..r] such that r - l + 1 < m, where m is the current length of the array.
  • The selected subarray is removed, and the remaining elements are concatenated to form the new array.
  • The game continues until only one element remains.

Alice aims to maximize the final element, while Bob aims to minimize it. Assuming both play optimally, return the value of the final remaining element.

 

Example 1:

Input: nums = [1,5,2]

Output: 2

Explanation:

One valid optimal strategy:

  • Alice removes [1], array becomes [5, 2].
  • Bob removes [5], array becomes [2]​​​​​​​. Thus, the answer is 2.

Example 2:

Input: nums = [3,7]

Output: 7

Explanation:

Alice removes [3], leaving the array [7]. Since Bob cannot play a turn now, the answer is 7.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

Solutions

Solution 1: Brain Teaser

Since Alice goes first, Alice can choose to remove all elements except the first and last elements, so the answer is at least $\max(nums[0], nums[n - 1])$.

For the cases of elements at indices $1, 2, …, n-2$ (the middle elements), even if Alice wants to keep any of these middle elements, Bob can choose to remove it, so the answer is at most $\max(nums[0], nums[n - 1])$.

Therefore, the answer is exactly $\max(nums[0], nums[n - 1])$.

The time complexity is $O(1)$ and the space complexity is $O(1)$.

  • class Solution {
    public int finalElement(int[] nums) {
        return Math.max(nums[0], nums[nums.length - 1]);
    }
}


  • class Solution {
public:
    int finalElement(vector<int>& nums) {
        return max(nums[0], nums.back());
    }
};


  • class Solution:
    def finalElement(self, nums: List[int]) -> int:
        return max(nums[0], nums[-1])


  • func finalElement(nums []int) int {
	return max(nums[0], nums[len(nums)-1])
}


  • function finalElement(nums: number[]): number {
    return Math.max(nums.at(0)!, nums.at(-1)!);
}

All Problems

All Solutions