Skip to content

3828. Final Element After Subarray Deletions

SourceWeekly Contest 487 Q2DifficultyMediumRating1591

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

Thinking

Each move deletes a proper subarray. Alice maximizes and Bob minimizes the last remaining value. \(n \le 10^5\) makes the game tree impossible.

Alice can delete the entire middle on the first move and leave one endpoint, so the answer is at least the larger endpoint.

Any interior value that is not yet last can still be deleted by Bob later, so Alice cannot lock it in.

With optimal play the result is exactly \(\max(nums[0],nums[n-1])\).

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)\).

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

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

1
2
3
4
5
6
class Solution {
public:
    int finalElement(vector<int>& nums) {
        return max(nums[0], nums.back());
    }
};

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

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

Comments