Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1240. Stone Game II

My accepted Python solution to LeetCode problem 1240, Stone Game II, running in 129ms.

  • Difficulty: Medium
  • Python
  • Runtime 129ms
  • Memory 18.5MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 129ms, memory 18.5MB, accepted 2026-01-02.

python
class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        # Suffix sum
        suffix = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            suffix[i] = suffix[i + 1] + piles[i]
        
        memo = {}
        
        def dp(i, m):
            if i >= n:
                return 0
            if (i, m) in memo:
                return memo[(i, m)]
            
            if i + 2 * m >= n:
                return suffix[i]
            
            max_stones = 0
            for x in range(1, 2 * m + 1):
                # Take x piles, opponent gets the rest optimally
                opponent_stones = dp(i + x, max(m, x))
                my_stones = suffix[i] - opponent_stones
                max_stones = max(max_stones, my_stones)
            
            memo[(i, m)] = max_stones
            return max_stones
        
        return dp(0, 1)

Source