Stone Game
Stone Game is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the Interval DP subpattern.
Problem statement
You are given an array of piles in piles, where each value is the number of stones in one pile. The piles remain in their original order, and two players take turns removing exactly one pile from either the left or right end of the remaining array.
The first player moves first. Each player keeps the stones they remove, and both players play optimally. Return true if the first player finishes with more stones than the second player; otherwise, return false. The input guarantees that a tie cannot occur.
Example 1:
Input: piles = [1,2] Output: true Explanation: The first player takes the pile containing 2 stones and leaves 1 stone, so the first player wins.
Example 2:
Input: piles = [4,1,2,6] Output: true Explanation: The first player can choose an optimal sequence of end removals that produces a strictly larger total than the second player.
Example 3:
Input: piles = [8,1,5,3,2,6] Output: true Explanation: With optimal play, the first player secures more stones; the odd total ensures the result is not a tie.
Constraints:
- 2 <= piles.length <= 500 - piles.length is even - 1 <= piles[i] <= 500 - The sum of all values in piles is odd - On each turn, a player removes exactly one pile from the left or right end of the remaining piles
Topics and companies
Topics: Dynamic Programming, Array, Math.
How to practise Stone Game on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(1) time and O(1) space.
Open Stone Game in the code editor, or read the Stone Game editorial for a worked solution with its approach and complexity analysis.
Where Stone Game sits in the DSA pattern sheet
- Dynamic Programming (DP) Patterns pattern guide
- Interval DP subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Stone Game
Other problems that use the same Interval DP and Dynamic Programming (DP) Patterns techniques:
- Burst Balloons — Hard, same subpattern
- Remove Boxes — Hard, same subpattern
- Stone Game II — Medium, same subpattern
- Best Time to Buy and Sell Stock — Easy, same pattern
- Best Time to Buy and Sell Stock II — Medium, same pattern
- Best Time to Buy and Sell Stock III — Hard, same pattern