title: Stone Game III
slug: stone-game-iii
difficulty: hard
leetcode_id: 1406
leetcode_url: https://leetcode.com/problems/stone-game-iii/
categories:
  - arrays
  - dynamic-programming
patterns:
  - slug: dynamic-programming
    is_optimal: true

function_signature: "def stone_game_iii(stone_value: list[int]) -> str:"

test_cases:
  visible:
    - input: { stone_value: [1, 2, 3, 7] }
      expected: "Bob"
    - input: { stone_value: [1, 2, 3, -9] }
      expected: "Alice"
    - input: { stone_value: [1, 2, 3, 6] }
      expected: "Tie"
  hidden:
    - input: { stone_value: [1] }
      expected: "Alice"
    - input: { stone_value: [-1, -2, -3] }
      expected: "Tie"
    - input: { stone_value: [1, 2, 3, -1, -2, -3, 7] }
      expected: "Alice"
    - input: { stone_value: [-1] }
      expected: "Bob"
    - input: { stone_value: [5, -2, -3, 4] }
      expected: "Alice"

description: |
  Alice and Bob continue their games with piles of stones. There are several stones **arranged in a row**, and each stone has an associated value which is an integer given in the array `stoneValue`.

  Alice and Bob take turns, with Alice starting first. On each player's turn, that player can take `1`, `2`, or `3` stones from the **first** remaining stones in the row.

  The score of each player is the sum of the values of the stones taken. The score of each player is `0` initially.

  The objective of the game is to end with the highest score, and the winner is the player with the highest score and there could be a tie. The game continues until all the stones have been taken.

  Assume Alice and Bob **play optimally**.

  Return `"Alice"` *if Alice will win*, `"Bob"` *if Bob will win*, or `"Tie"` *if they will end the game with the same score*.

constraints: |
  - `1 <= stoneValue.length <= 5 * 10^4`
  - `-1000 <= stoneValue[i] <= 1000`

examples:
  - input: "stoneValue = [1,2,3,7]"
    output: '"Bob"'
    explanation: "Alice will always lose. Her best move will be to take three piles and the score becomes 6. Now the score of Bob is 7 and Bob wins."
  - input: "stoneValue = [1,2,3,-9]"
    output: '"Alice"'
    explanation: "Alice must choose all the three piles at the first move to win and leave Bob with negative score. If Alice chooses one pile her score will be 1 and the next move Bob's score becomes 5. In the next move, Alice will take the pile with value = -9 and lose."
  - input: "stoneValue = [1,2,3,6]"
    output: '"Tie"'
    explanation: "Alice cannot win this game. She can end the game in a draw if she decided to choose all the first three piles, otherwise she will lose."

explanation:
  intuition: |
    Imagine you're at a buffet line where each dish has a "value" — some positive (delicious) and some negative (terrible). You and your opponent take turns, and each turn you must take 1, 2, or 3 consecutive dishes from the front of the line. Both of you want to maximize your own total value.

    The key insight is the **zero-sum nature** of this game: whatever stones remain after you pick, your opponent will play optimally on those remaining stones. So instead of tracking both players' scores separately, we can think in terms of **relative advantage**.

    Define `dp[i]` as the maximum **score difference** (current player's score minus opponent's score) that the current player can achieve starting from index `i`. When it's your turn at position `i`:

    - If you take stones `i` to `i+k-1` (where `k` is 1, 2, or 3), you gain those values
    - Then your opponent plays optimally from position `i+k`, achieving `dp[i+k]` for themselves
    - Your relative advantage becomes: `sum of stones taken - dp[i+k]`

    The subtraction of `dp[i+k]` captures the **minimax** principle — your opponent's best outcome becomes your deficit.

    At the end, if `dp[0] > 0`, Alice (who starts) has a positive advantage and wins. If `dp[0] < 0`, Bob wins. If `dp[0] == 0`, it's a tie.

  approach: |
    We solve this using **Dynamic Programming** with state representing the relative score difference:

    **Step 1: Define the DP state**

    - `dp[i]`: Maximum score difference (current player minus opponent) achievable starting from index `i`
    - Base case: `dp[n] = 0` (no stones left means no advantage)

    &nbsp;

    **Step 2: Build the recurrence relation**

    - At each position `i`, the current player can take 1, 2, or 3 stones
    - For each choice `k` (1, 2, or 3):
      - Player gains: `stoneValue[i] + stoneValue[i+1] + ... + stoneValue[i+k-1]`
      - Opponent then achieves: `dp[i+k]` from the remaining stones
      - Net advantage: `sum of k stones - dp[i+k]`
    - Choose the maximum among all valid options

    &nbsp;

    **Step 3: Iterate backwards from the end**

    - Process positions from `n-1` down to `0`
    - Use a suffix sum to efficiently calculate the sum of stones taken
    - Track `dp[i+1]`, `dp[i+2]`, `dp[i+3]` for the three possible moves

    &nbsp;

    **Step 4: Determine the winner**

    - If `dp[0] > 0`: Alice wins (she has positive advantage)
    - If `dp[0] < 0`: Bob wins (Alice has negative advantage, meaning Bob is ahead)
    - If `dp[0] == 0`: Tie

  common_pitfalls:
    - title: Tracking Both Scores Separately
      description: |
        A natural first instinct is to track Alice's score and Bob's score as separate states. This leads to a 2D DP with states like `dp[i][aliceScore][bobScore]`, which has prohibitive complexity.

        The insight is that we only care about the **difference** between scores, not the absolute values. This reduces the problem to a single dimension: the relative advantage of whoever is currently playing.
      wrong_approach: "Track separate scores for Alice and Bob"
      correct_approach: "Track score difference (current player - opponent)"

    - title: Forgetting Negative Stone Values
      description: |
        Unlike simpler stone game variants, this problem has **negative values**. This means sometimes the optimal play is to take fewer stones to force your opponent to take negative ones.

        For example, with `[1, 2, 3, -9]`, Alice's optimal move is to take all three positive stones (sum = 6) and leave Bob with just the -9, giving Bob a score of -9. Alice wins 6 to -9.

        If Alice only took one stone, Bob could take `[2, 3]` (sum = 5) and leave Alice with -9. Bob would win.
      wrong_approach: "Assume taking more stones is always better"
      correct_approach: "Consider all 1, 2, 3 stone options and pick the best difference"

    - title: Off-by-One Errors in Suffix Sums
      description: |
        When calculating the sum of the next `k` stones, be careful with indices. The sum from index `i` taking `k` stones is `suffixSum[i] - suffixSum[i+k]`, not `suffixSum[i+k]`.

        Also ensure you handle the case where `i + k > n` by treating out-of-bounds `dp` values as 0.
      wrong_approach: "Incorrect suffix sum indexing"
      correct_approach: "Use suffixSum[i] - suffixSum[min(i+k, n)] for sum of k stones"

  key_takeaways:
    - "**Minimax principle**: In two-player zero-sum games, maximizing your advantage equals minimizing your opponent's advantage"
    - "**Score difference DP**: Track relative advantage instead of absolute scores to reduce state complexity"
    - "**Backward iteration**: Process from end to start, as each state depends on future states"
    - "**Foundation for game theory**: This pattern applies to many competitive game problems (Stone Game variants, Nim, etc.)"

  time_complexity: "O(n). We compute each `dp[i]` exactly once, and each computation considers at most 3 previous states."
  space_complexity: "O(n) for the DP array. Can be optimized to O(1) since we only need the last 3 DP values."

solutions:
  - approach_name: Dynamic Programming (Score Difference)
    is_optimal: true
    code: |
      def stone_game_iii(stone_value: list[int]) -> str:
          n = len(stone_value)

          # dp[i] = max score difference (current player - opponent)
          # starting from index i
          # We need dp[i+1], dp[i+2], dp[i+3], so use array of size n+1
          dp = [0] * (n + 1)

          # Suffix sum for efficient range sum calculation
          suffix_sum = [0] * (n + 1)
          for i in range(n - 1, -1, -1):
              suffix_sum[i] = suffix_sum[i + 1] + stone_value[i]

          # Fill DP from right to left
          for i in range(n - 1, -1, -1):
              # Try taking 1, 2, or 3 stones
              # Initialize to negative infinity to find maximum
              dp[i] = float('-inf')

              for k in range(1, 4):  # k = 1, 2, or 3 stones
                  if i + k <= n:
                      # Sum of stones taken: suffix_sum[i] - suffix_sum[i+k]
                      stones_taken = suffix_sum[i] - suffix_sum[i + k]
                      # Our advantage = stones we get - opponent's best outcome
                      dp[i] = max(dp[i], stones_taken - dp[i + k])

          # Determine winner based on Alice's advantage (she starts at index 0)
          if dp[0] > 0:
              return "Alice"
          elif dp[0] < 0:
              return "Bob"
          else:
              return "Tie"
    explanation: |
      **Time Complexity:** O(n) — Single pass through the array from right to left, with O(1) work per position.

      **Space Complexity:** O(n) — For the DP array and suffix sum array.

      We define `dp[i]` as the maximum score difference achievable by the current player starting from index `i`. By iterating backwards and considering all three choices (take 1, 2, or 3 stones), we build up the optimal strategy. The minimax principle is captured by subtracting `dp[i+k]` — the opponent's best outcome becomes our deficit.

  - approach_name: Space-Optimized DP
    is_optimal: true
    code: |
      def stone_game_iii(stone_value: list[int]) -> str:
          n = len(stone_value)

          # Only need last 3 DP values
          # dp_next[0] = dp[i+1], dp_next[1] = dp[i+2], dp_next[2] = dp[i+3]
          dp_next = [0, 0, 0]

          # Process from right to left
          suffix = 0  # Running suffix sum starting from position i

          for i in range(n - 1, -1, -1):
              suffix += stone_value[i]

              # Try taking 1, 2, or 3 stones
              best = float('-inf')
              take_sum = 0

              for k in range(1, 4):
                  if i + k - 1 < n:
                      take_sum += stone_value[i + k - 1]
                      # Opponent's best is dp_next[k-1] (which is dp[i+k])
                      opponent_best = dp_next[k - 1] if k <= 3 else 0
                      best = max(best, take_sum - opponent_best)

              # Shift the window: dp[i+3] <- dp[i+2] <- dp[i+1] <- dp[i]
              dp_next[2] = dp_next[1]
              dp_next[1] = dp_next[0]
              dp_next[0] = best

          # dp_next[0] now holds dp[0], Alice's maximum advantage
          if dp_next[0] > 0:
              return "Alice"
          elif dp_next[0] < 0:
              return "Bob"
          else:
              return "Tie"
    explanation: |
      **Time Complexity:** O(n) — Single pass through the array.

      **Space Complexity:** O(1) — Only stores 3 previous DP values.

      This optimized version recognizes that `dp[i]` only depends on `dp[i+1]`, `dp[i+2]`, and `dp[i+3]`. By maintaining a sliding window of just 3 values, we reduce space from O(n) to O(1) while preserving the same logic.

  - approach_name: Recursive with Memoization
    is_optimal: false
    code: |
      def stone_game_iii(stone_value: list[int]) -> str:
          n = len(stone_value)
          memo = {}

          def dp(i: int) -> int:
              """Return max score difference for current player starting at i."""
              if i >= n:
                  return 0

              if i in memo:
                  return memo[i]

              # Try taking 1, 2, or 3 stones
              best = float('-inf')
              take_sum = 0

              for k in range(1, 4):
                  if i + k - 1 < n:
                      take_sum += stone_value[i + k - 1]
                      # Our advantage = stones taken - opponent's best
                      best = max(best, take_sum - dp(i + k))

              memo[i] = best
              return best

          result = dp(0)

          if result > 0:
              return "Alice"
          elif result < 0:
              return "Bob"
          else:
              return "Tie"
    explanation: |
      **Time Complexity:** O(n) — Each state computed once due to memoization.

      **Space Complexity:** O(n) — For memoization dictionary and recursion stack.

      This top-down approach may be more intuitive for some. We recursively compute the best score difference from each position, caching results to avoid recomputation. The logic is identical to the bottom-up DP but expressed recursively.
