LeetCode 3828 - Final Element After Subarray Deletions

We are given an integer array nums. Two players, Alice and Bob, repeatedly remove a contiguous subarray from the current array. The only restriction is that the removed subarray cannot be the entire current array, so after every move at least one element remains.

leetcodemediumarraymathbrainteasergame-theory

LeetCode Problem 3828

Difficulty: 🟡 Medium
Topics: Array, Math, Brainteaser, Game Theory

Solution

Problem Understanding

We are given an integer array nums. Two players, Alice and Bob, repeatedly remove a contiguous subarray from the current array. The only restriction is that the removed subarray cannot be the entire current array, so after every move at least one element remains.

After a subarray is removed, the remaining elements are concatenated together to form the new array. The game continues until exactly one element remains.

Alice moves first and wants the final remaining element to be as large as possible. Bob wants it to be as small as possible. Both players play optimally.

The input is simply the starting array. The output is the value of the single element that remains at the end of the game when both players make optimal decisions.

The constraints are large, up to 10^5 elements, which immediately tells us that any simulation of the game tree is impossible. A naive minimax solution would have an enormous branching factor and exponential complexity.

Several edge cases are worth noting:

  • An array of length 1 already contains a single remaining element, so that value is the answer.
  • An array of length 2 allows Alice to remove either element immediately and end the game.
  • Large arrays cannot be processed with any recursive game search.
  • The operation removes a contiguous block, which means some structural properties of the array endpoints become very important.

Approaches

Brute Force

A brute force solution would model the game exactly.

For every state of the array, the current player would try every valid subarray deletion. Alice would choose the move that maximizes the eventual result, while Bob would choose the move that minimizes it. This is a standard minimax search.

The approach is correct because it explicitly explores all legal game states and applies optimal play at every turn.

Unfortunately, it is completely impractical. Even for small arrays, the number of possible states grows explosively. Every move can generate many new arrays, and the depth of the game can be as large as n - 1.

Key Insight

The crucial observation is that after deleting a contiguous subarray, at least one of the current array's endpoints must survive.

Suppose the current array is:

[left, ..., right]

A deletion can:

  • Remove a prefix, preserving right
  • Remove a suffix, preserving left
  • Remove a middle segment, preserving both endpoints

It is impossible to delete both endpoints in a single move.

This leads to a very strong invariant.

Let:

  • A(nums) be the game value when it is Alice's turn.
  • B(nums) be the game value when it is Bob's turn.

For any array:

  • A(nums) = max(first element, last element)
  • B(nums) = min(first element, last element)

The proof follows by induction.

Since the game starts with Alice's turn, the answer is simply:

max(nums[0], nums[n - 1])

No other element can ever be forced to beat the larger endpoint under optimal play.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Explores the full minimax game tree
Optimal O(1) O(1) Answer is the maximum of the two endpoints

Algorithm Walkthrough

  1. Read the first element of the array.
  2. Read the last element of the array.
  3. Since Alice moves first, and the game value on Alice's turn is always the larger of the current endpoints, compute max(first, last).
  4. Return that value.

Why it works

Consider any position whose endpoints are L and R.

If it is Alice's turn, she can immediately leave only L or only R by deleting the remaining n - 1 elements. Therefore she can guarantee at least max(L, R).

On the other hand, after any legal move, at least one of L or R remains an endpoint of the new array. By induction, Bob's value on the resulting position is the minimum of its endpoints. Since one of those endpoints is either L or R, that minimum can never exceed max(L, R).

Therefore Alice's optimal value is exactly max(L, R).

Applying the symmetric argument for Bob gives min(L, R).

Since the initial turn belongs to Alice, the final answer is max(nums[0], nums[n - 1]).

Python Solution

from typing import List

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

The implementation directly encodes the game theoretic result.

The first and last elements are the only values that matter. The induction proof shows that Alice's optimal value is always the larger endpoint of the current array. Since the game starts on the original array, we simply return the maximum of the first and last elements.

No simulation, recursion, or dynamic programming is required.

Go Solution

func finalElement(nums []int) int {
    if nums[0] > nums[len(nums)-1] {
        return nums[0]
    }
    return nums[len(nums)-1]
}

The Go implementation is identical in logic to the Python version.

The solution accesses the first and last elements and returns the larger one. Since all values are at most 10^5, integer overflow is not a concern. No additional memory allocation is needed.

Worked Examples

Example 1

Input:

nums = [1, 5, 2]

Endpoints:

First Last
1 2

Alice's value is:

max(1, 2) = 2

Return:

2

One optimal play is:

Turn Action Array
Alice Remove [1] [5, 2]
Bob Remove [5] [2]

Final element:

2

Example 2

Input:

nums = [3, 7]

Endpoints:

First Last
3 7

Compute:

max(3, 7) = 7

Return:

7

Alice simply removes [3], leaving [7].

Complexity Analysis

Measure Complexity Explanation
Time O(1) Only two array accesses and one comparison
Space O(1) No auxiliary storage is used

The solution does not depend on the length of the array beyond accessing the first and last positions. Therefore both time and space complexity are constant.

Test Cases

sol = Solution()

assert sol.finalElement([1, 5, 2]) == 2          # example 1
assert sol.finalElement([3, 7]) == 7             # example 2

assert sol.finalElement([42]) == 42              # single element
assert sol.finalElement([5, 1]) == 5             # larger first endpoint
assert sol.finalElement([1, 5]) == 5             # larger last endpoint

assert sol.finalElement([1, 100, 100, 2]) == 2   # large interior values do not matter
assert sol.finalElement([9, 1, 2, 3]) == 9       # first endpoint dominates
assert sol.finalElement([1, 2, 3, 9]) == 9       # last endpoint dominates

assert sol.finalElement([7, 7, 7, 7]) == 7       # all equal
assert sol.finalElement([10, 1, 10]) == 10       # equal endpoints

assert sol.finalElement([100000, 1, 1, 1]) == 100000  # max constraint value at front
assert sol.finalElement([1, 1, 1, 100000]) == 100000  # max constraint value at end

Test Summary

Test Why
[1,5,2] Official example
[3,7] Official example
[42] Length 1 boundary case
[5,1] Larger first endpoint
[1,5] Larger last endpoint
[1,100,100,2] Interior values do not affect result
[9,1,2,3] First endpoint determines answer
[1,2,3,9] Last endpoint determines answer
[7,7,7,7] All values equal
[10,1,10] Equal endpoints
[100000,1,1,1] Maximum value at first position
[1,1,1,100000] Maximum value at last position

Edge Cases

Array of Length One

When nums contains only a single element, the game is already over before any moves are made. A careless implementation might assume there are always two endpoints to compare, but in this case the first and last elements are the same element. Returning max(nums[0], nums[-1]) correctly returns that value.

Very Large Interior Values

Consider:

[1, 100000, 100000, 2]

A common mistake is to assume Alice can somehow force one of the large middle values. The game structure prevents this. The induction proof shows that only the endpoints matter under optimal play. The implementation correctly returns 2.

Equal Endpoints

Consider:

[10, 1, 2, 3, 10]

Both endpoints have the same value. Regardless of which endpoint Alice ultimately preserves, the answer is 10. The implementation naturally handles this case because max(10, 10) equals 10.

Maximum Input Size

The array may contain up to 100000 elements. Any minimax search, dynamic programming table, or simulation would be far too slow. The constant time endpoint comparison easily handles the largest possible input size.