Scale Engineer

Stone Game VII

Med
#1550Time: O(n^2). The nested loops run O(n^2) times, and each step is O(1).Space: O(n). We use a 1D array `dp` of size `n` and a prefix sum array of size `n+1`.1 company
Patterns
MathDynamic ProgrammingGame Theory
Data structures
Array
Companies
Dunzo

Prompt

Alice and Bob take turns playing a game, with Alice starting first.

There are n stones arranged in a row. On each player's turn, they can remove either the leftmost stone or the rightmost stone from the row and receive points equal to the sum of the remaining stones' values in the row. The winner is the one with the higher score when there are no stones left to remove.

Bob found that he will always lose this game (poor Bob, he always loses), so he decided to minimize the score's difference. Alice's goal is to maximize the difference in the score.

Given an array of integers stones where stones[i] represents the value of the ith stone from the left, return the difference in Alice and Bob's score if they both play optimally.

 

Example 1:

Input: stones = [5,3,1,4,2]
Output: 6
Explanation: 
- Alice removes 2 and gets 5 + 3 + 1 + 4 = 13 points. Alice = 13, Bob = 0, stones = [5,3,1,4].
- Bob removes 5 and gets 3 + 1 + 4 = 8 points. Alice = 13, Bob = 8, stones = [3,1,4].
- Alice removes 3 and gets 1 + 4 = 5 points. Alice = 18, Bob = 8, stones = [1,4].
- Bob removes 1 and gets 4 points. Alice = 18, Bob = 12, stones = [4].
- Alice removes 4 and gets 0 points. Alice = 18, Bob = 12, stones = [].
The score difference is 18 - 12 = 6.

Example 2:

Input: stones = [7,90,5,1,100,10,10,2]
Output: 122

 

Constraints:

  • n == stones.length
  • 2 <= n <= 1000
  • 1 <= stones[i] <= 1000

Approaches

4 approaches with complexity analysis and trade-offs.

This approach optimizes the space complexity of the bottom-up DP solution. By observing the state transitions, we can see that to compute the values for a subarray of a certain length, we only need the results for subarrays of the immediately smaller length. This means to compute the current row i of our DP table, we only need the next row i+1. This dependency allows us to reduce the space from O(n^2) to O(n).

Algorithm

  • Create a prefix sum array for O(1) sum calculations.
  • Create a 1D DP array dp[n], initialized to 0.
  • Iterate the start index i from n-2 down to 0.
  • In the inner loop, iterate the end index j from i+1 up to n-1.
  • Inside the inner loop, calculate the two possible differences: a. diff1 = (prefixSum[j+1] - prefixSum[i+1]) - dp[j]. Here dp[j] holds the value from the previous outer loop, which corresponds to dp[i+1][j]. b. diff2 = (prefixSum[j] - prefixSum[i]) - dp[j-1]. Here dp[j-1] holds the value just computed in the current inner loop, which corresponds to dp[i][j-1].
  • Update dp[j] with max(diff1, diff2).
  • After the loops, dp[n-1] will contain the result for the entire array stones[0...n-1].

Walkthrough

The recurrence is dp[i][j] = max(sum(i+1, j) - dp[i+1][j], sum(i, j-1) - dp[i][j-1]). Let's iterate by the starting index i from n-2 down to 0, and the ending index j from i+1 up to n-1. When we compute dp[i][j], we need dp[i+1][j] (from the 'next' row i+1) and dp[i][j-1] (from the 'current' row i, but a previous column). This structure allows for space optimization. We can use a 1D array, say dp[n]. Let dp[j] represent the value for the current row i and column j. When we are calculating the row for i, the dp array will hold the values from the previous iteration, which corresponds to row i+1. The recurrence becomes: dp[j] = max(sum(i+1, j) - dp[j], sum(i, j-1) - dp[j-1]), where we update the dp array in place.

class Solution {    public int stoneGameVII(int[] stones) {        int n = stones.length;        int[] prefixSum = new int[n + 1];        for (int i = 0; i < n; i++) {            prefixSum[i + 1] = prefixSum[i] + stones[i];        }         int[] dp = new int[n];         // i is the starting index of the subarray        for (int i = n - 2; i >= 0; i--) {            // j is the ending index of the subarray            for (int j = i + 1; j < n; j++) {                // Sum of stones from i+1 to j                int sumTakeLeft = prefixSum[j + 1] - prefixSum[i + 1];                // Sum of stones from i to j-1                int sumTakeRight = prefixSum[j] - prefixSum[i];                 // dp[j] currently holds dp[i+1][j] from the previous outer loop iteration                // dp[j-1] holds dp[i][j-1] from the current inner loop iteration                int diff1 = sumTakeLeft - dp[j];                int diff2 = sumTakeRight - dp[j - 1];                 dp[j] = Math.max(diff1, diff2);            }        }         return dp[n - 1];    }}

Complexity

Time

O(n^2). The nested loops run O(n^2) times, and each step is O(1).

Space

O(n). We use a 1D array `dp` of size `n` and a prefix sum array of size `n+1`.

Trade-offs

Pros

  • Most efficient in terms of space complexity.

  • Maintains the optimal O(n^2) time complexity.

Cons

  • The logic for in-place updates and loop directions can be tricky to reason about compared to the O(n^2) space solution.

Solutions

class Solution {private  int[] s;private  Integer[][] f;public  int stoneGameVII(int[] stones) {    int n = stones.length;    s = new int[n + 1];    f = new Integer[n][n];    for (int i = 0; i < n; ++i) {      s[i + 1] = s[i] + stones[i];    }    return dfs(0, n - 1);  }private  int dfs(int i, int j) {    if (i > j) {      return 0;    }    if (f[i][j] != null) {      return f[i][j];    }    int a = s[j + 1] - s[i + 1] - dfs(i + 1, j);    int b = s[j] - s[i] - dfs(i, j - 1);    return f[i][j] = Math.max(a, b);  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem