Practice/Amazon/Leetcode 486. Predict the Winner

Leetcode 486. Predict the Winner

CodingMust

Problem

Two players are competing in a stone collection game. They have a row of stones, each with a certain point value. Players take turns selecting a stone from either the leftmost or rightmost position of the remaining row. The selected stone is removed and its value is added to that player's score.

Player 1 always goes first. Both players play optimally, meaning each player makes the move that maximizes their chances of winning.

Your task is to determine whether Player 2 can guarantee a win or at least a tie against Player 1. Return true if Player 2 can guarantee not losing (win or tie), and false otherwise.

Requirements

1. Implement a function that takes an array of stone values
2. Determine if Player 2 can guarantee a non-loss with optimal play
3. Both players choose optimally to maximize their own score
4. A tie counts as Player 2 achieving their goal (return true)

Constraints

• 1 ≤ stones.length ≤ 20
• 0 ≤ stones[i] ≤ 10^7
• Time complexity should be polynomial
• Space complexity should be reasonable for the input size

Examples

Example 1:

` Input: stones = [1, 5, 2] Output: false Explanation:

• Player 1 can take 2 from the right (score: 2)
• Player 2 takes 5 (score: 5)
• Player 1 takes 1 (final score: 3) Player 2 wins 5-3, so return true...

Actually with optimal play:

• Player 1 takes 1 from left (score: 1)
• Player 2 must choose between 5 and 2, takes 2 (score: 2)
• Player 1 takes 5 (final score: 6) Player 1 wins 6-2, so return false. `

Example 2:

Input: stones = [1, 5, 233, 7] Output: true Explanation: Player 2 can guarantee at least a tie with optimal strategy.

Example 3:

Input: stones = [10] Output: false Explanation: Player 1 takes the only stone and wins 10-0.