Practice/Google/Leetcode 877. Stone Game

Leetcode 877. Stone Game

CodingMust

Problem

Two players are competing in a coin collection game. The coins are arranged in a line, represented as an array where each element indicates the value of coins in that position. Players alternate turns, with Player 1 going first. On each turn, a player must take all coins from either the leftmost or rightmost position in the remaining line.

Both players play optimally to maximize their own total coin value. Your task is to determine whether Player 1 can guarantee winning the game (collecting strictly more coins than Player 2).

Requirements

1. Return true if Player 1 can force a win with optimal play
2. Return false if Player 2 can avoid losing (tie or win)
3. Both players make optimal decisions at every turn
4. Players can only take from the ends of the remaining array

Constraints

• 2 <= coins.length <= 500
• coins.length is even
• 1 <= coins[i] <= 1000
• The sum of all coin values is odd (no ties possible with optimal play)
• Time complexity: aim for O(n²)
• Space complexity: aim for O(n²) or better

Examples

Example 1:

` Input: coins = [5, 3, 7, 10] Output: true Explanation:

• Player 1 takes 10 (right end): [5, 3, 7] → Player 1 total = 10
• Player 2 takes 7 (right end): [5, 3] → Player 2 total = 7
• Player 1 takes 5 (left end): [3] → Player 1 total = 15
• Player 2 takes 3: [] → Player 2 total = 10 Player 1 wins with 15 > 10 `

Example 2:

Input: coins = [3, 7] Output: true Explanation: Player 1 takes 7, Player 2 takes 3. Player 1 wins with 7 > 3.

Example 3:

Input: coins = [2, 1, 9, 5] Output: false Explanation: With optimal play from both sides, Player 2 can prevent Player 1 from winning.