Stone Game III

Stone Game III is a Hard 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 1D Array (Fibonacci Style) subpattern.

Problem statement

You are given an integer array stoneValue representing a row of stones. Alice plays first, and Bob plays second. On each turn, the current player must take one, two, or three stones from the left end of the remaining row and add the values of those stones to that player's score.

The players continue taking stones until no stones remain. Both players choose moves that maximize their own final score. Return exactly "Alice" if Alice's score is higher, "Bob" if Bob's score is higher, or "Tie" if the scores are equal.

Implement stoneGameIII in the Solution class with the specified signature. The method receives stoneValue and returns one of the three required strings.

Example 1:

Input: stoneValue = [0] Output: "Tie" Explanation: Alice must take the only stone, giving both players a final score of 0.

Example 2:

Input: stoneValue = [-5,-1,-1,-1] Output: "Bob" Explanation: No matter whether Alice takes one, two, three, or all four stones, optimal play gives Bob a strictly greater final score.

Example 3:

Input: stoneValue = [4,-6,2] Output: "Alice" Explanation: Alice can take all three stones for a total of 0, while taking fewer stones allows Bob to finish with a lower score.

Constraints:

- 1 <= stoneValue.length <= 10^5 - -1000 <= stoneValue[i] <= 1000 - stoneValue contains only integers - Alice always takes the first turn - On every turn, a player takes exactly 1, 2, or 3 stones, unless fewer than 3 stones remain - Every stone is taken exactly once

Topics and companies

Topics: Array, Dynamic Programming, Memoization.

How to practise Stone Game III 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(n) time and O(n) space.

Open Stone Game III in the code editor, or read the Stone Game III editorial for a worked solution with its approach and complexity analysis.

Where Stone Game III sits in the DSA pattern sheet

Problems related to Stone Game III

Other problems that use the same 1D Array (Fibonacci Style) and Dynamic Programming (DP) Patterns techniques:

Preparing this workspace.