End-Picking Number Game: Can the First Player Win Under Optimal Play?
Company: Waymo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Two players play a game on a row of non-negative integers `nums`. They alternate turns, and Player 1 moves first. On each turn, the current player removes either the leftmost or the rightmost remaining number and adds it to their own score. The game ends when no numbers remain.
Both players play optimally. Return whether Player 1 can finish with a score at least as large as Player 2's.
### Function Signature
```python
def first_player_can_win(nums: list[int]) -> bool:
```
### Rules
- Both scores start at 0.
- "Optimally" means each player always chooses the move that maximizes their own final score minus the opponent's final score, assuming the opponent does the same.
- Return `True` if Player 1's final score is greater than or equal to Player 2's under optimal play (a tie counts as a win for Player 1), and `False` otherwise.
### Constraints
- `1 <= len(nums) <= 20`
- `0 <= nums[i] <= 10^7`
### Examples
**Example 1**
- Input: `nums = [2, 9, 4]`
- Output: `False`
- Explanation: Whichever end Player 1 takes, Player 2 can then take 9. Player 1's best total is 6 against 9.
**Example 2**
- Input: `nums = [3, 7, 2, 2]`
- Output: `True`
- Explanation: Player 1 takes the rightmost 2, leaving `[3, 7, 2]`. Whichever end Player 2 takes, Player 1 can then take 7. Player 1 finishes with 9 against Player 2's 5.
**Example 3**
- Input: `nums = [5]`
- Output: `True`
Overview: Two players alternately take a number from either end of a row and add it to their score; decide whether the first player can finish with at least as many points as the second under optimal play. Tests minimax reasoning and memoized game-state search.
Two players play a game on a row of non-negative integers `nums`. They alternate turns, and Player 1 moves first. On each turn, the current player removes either the leftmost or the rightmost remaining number and adds it to their own score. Both scores start at 0, and the game ends when no numbers remain.
Both players play optimally: on every turn, the player to move picks the end that maximizes their own final score minus the opponent's final score, assuming the opponent plays the same way.
Implement `first_player_can_win(nums)` and return `True` if Player 1's final score is **greater than or equal to** Player 2's under optimal play (a tie counts as a win for Player 1), and `False` otherwise.
**Constraints**
- `1 <= len(nums) <= 20`
- `0 <= nums[i] <= 10^7`
- Every total and every score difference is at most `2 * 10^8` in absolute value, so it fits in a signed 32-bit integer.
**Example 1**
- Input: `nums = [2, 9, 4]`
- Output: `False`
- Explanation: Whichever end Player 1 takes, Player 2 can then take 9. Player 1's best total is 6 against 9.
**Example 2**
- Input: `nums = [3, 7, 2, 2]`
- Output: `True`
- Explanation: Player 1 takes the rightmost 2, leaving `[3, 7, 2]`. Whichever end Player 2 takes, Player 1 can then take 7. Player 1 finishes with 9 against Player 2's 5.
**Example 3**
- Input: `nums = [5]`
- Output: `True`
Constraints
- 1 <= len(nums) <= 20
- 0 <= nums[i] <= 10^7
- Every total and every score difference fits in a signed 32-bit integer (absolute value at most 2 * 10^8)
Examples
Input: ([2, 9, 4],)
Expected Output: False
Input: ([3, 7, 2, 2],)
Expected Output: True
Hints
- Always grabbing the larger end is not enough: a small grab now can hand your opponent a much larger number next turn.
- Whatever moves have been made, the numbers left always form one contiguous block nums[i..j]. What single value about that block would tell the player to move which end to take?
- Measure a block by the best margin (your total minus your opponent's) the player to move can guarantee on it. After you take one end, your opponent faces a smaller block with the roles swapped.