Stone Game (Optimal Strategy)

📋

Problem

Imagine two players taking turns to pick stones from either end of a row of piles, each trying to maximize their own total stones collected. How can one determine if the first player can always win assuming both play optimally?

Given an array piles where piles[i] represents the number of stones in the i-th pile, two players (Alex and Lee) take turns picking a pile from either the start or the end of the row. Both players play optimally. Return true if Alex can win (get more stones than Lee), otherwise false.

2 ≤ piles.length ≤ 500piles.length is even1 ≤ piles[i] ≤ 500

Edge cases: All piles have the same number of stones → Alex always wins or tiesOnly two piles → Alex picks the larger pile and winsPiles with increasing values → Alex picks optimally to maximize gain

</>

IDE

def stoneGame(piles: list[int]) -> bool:public boolean stoneGame(int[] piles)bool stoneGame(vector<int>& piles)function stoneGame(piles)

def stoneGame(piles):
    # Write your solution here
    pass

class Solution {
    public boolean stoneGame(int[] piles) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool stoneGame(vector<int>& piles) {
    // Write your solution here
    return false;
}

function stoneGame(piles) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: falseUsing a greedy approach that picks the largest pile first without considering future moves.✅ Implement interval DP with dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]) to consider all subproblems.

Wrong: falseIncorrect handling of base cases, especially intervals of length 1 or 2.✅ Initialize dp[i][i] = piles[i] and handle intervals of length 2 explicitly in DP.

Wrong: falseOff-by-one errors in DP indices causing incorrect subproblem results.✅ Carefully manage dp indices and ensure loops and recursion boundaries are correct.

Wrong: falseAllowing multiple picks per turn (unbounded) instead of exactly one pile per turn.✅ Restrict picks to one pile per turn by defining dp over intervals and alternating turns.

Wrong: TLEUsing pure recursion without memoization leading to exponential time complexity.✅ Implement memoization or bottom-up DP to achieve O(n^2) time complexity.

✓

Test Cases

Focus on handling base cases and small inputs correctly before tackling edge cases.

Review your DP indexing and avoid greedy shortcuts to handle corner cases.

Optimize your solution to O(n^2) DP to handle large inputs efficiently.

t1_01basic

Input{"piles":[5,3,4,5]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Alex picks 5 from start, Lee picks 5 from end, Alex picks 4, Lee picks 3. Alex total = 9, Lee total = 8, so Alex wins.

💡 Consider the game as a zero-sum game where each player tries to maximize their score difference.

💡 Use interval DP to compute the maximum score difference the current player can achieve from piles[i..j].

💡 Define dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]); Alex wins if dp[0][n-1] > 0.

Why it failed: Returned false or incorrect result - likely missed the alternating turn logic or the score difference calculation. Fix by implementing dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]).

✓ Correctly computes the optimal score difference and returns true for Alex winning.

t1_02basic

Input{"piles":[3,9,1,2]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Alex picks 3 or 2 first, but optimal play leads Alex to win with total stones more than Lee.

💡 Try simulating both choices at each turn and pick the one maximizing the difference.

💡 Use memoization or bottom-up DP to avoid recomputing overlapping subproblems.

💡 Check dp[0][n-1] > 0 to decide if Alex wins.

Why it failed: Incorrect false output - likely greedy picking largest pile first without considering future consequences. Fix by using interval DP to consider all subproblems.

✓ Correctly handles non-trivial pile values and returns true for Alex winning.

t2_01edge

Input{"piles":[10,10,10,10]}

Expectedfalse

⏱ Performance - must finish in 2000ms

All piles have the same stones; Alex can always tie or win by picking first.

💡 Consider what happens when all piles have equal stones.

💡 Check if your DP handles equal values correctly without bias.

💡 Ensure dp[i][j] calculation does not assume strict inequality in piles values.

Why it failed: Fails on equal piles by returning false - likely incorrect tie handling or strict inequality assumptions. Fix by allowing dp to handle equal values correctly.

✓ Correctly returns true when all piles are equal.

t2_02edge

Input{"piles":[7,3]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Only two piles; Alex picks the larger pile (7) and wins immediately.

💡 Check base cases where only two piles exist.

💡 Ensure your DP or recursion correctly handles intervals of length 2.

💡 Return true if first player's pick is larger than second player's.

Why it failed: Fails two-pile case by returning false - likely base case dp[i][i+1] not handled properly. Fix by explicitly handling intervals of length 2.

✓ Correctly returns true for two piles with first pick larger.

t2_03edge

Input{"piles":[1,2,3,4,5,6]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Piles with increasing values; Alex picks optimally to maximize gain and wins.

💡 Test if your solution handles increasing sequences correctly.

💡 Verify dp transitions consider both ends and future consequences.

💡 Check dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]) for correctness.

Why it failed: Fails increasing sequence by returning false - likely greedy approach picking largest pile first without interval DP. Fix by implementing full interval DP.

✓ Correctly returns true for increasing piles.

t3_01corner

Input{"piles":[1,100,1,100,1,100]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Greedy trap: picking the largest pile first is not always optimal; interval DP needed.

💡 Beware of greedy strategies that pick the largest pile immediately.

💡 Use interval DP to consider future consequences of each pick.

💡 Implement dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]) to avoid greedy traps.

Why it failed: Fails greedy trap by returning false - likely greedy picking largest pile first without DP. Fix by using interval DP to evaluate all options.

✓ Correctly handles greedy trap and returns true.

t3_02corner

Input{"piles":[500,1,500,1,500,1]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Off-by-one error test: DP indices must be carefully managed to avoid incorrect subproblem results.

💡 Check your DP indexing carefully to avoid off-by-one errors.

💡 Ensure base cases dp[i][i] are initialized correctly.

💡 Verify recursive calls or loops use correct boundaries.

Why it failed: Fails due to off-by-one error in dp indices causing wrong results. Fix by carefully adjusting dp boundaries and base cases.

✓ Correctly handles dp indexing and returns true.

t3_03corner

Input{"piles":[2,2,2,2,2,2,2,2]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Confusion between 0/1 and unbounded picks: only one pile can be taken per turn.

💡 Remember only one pile can be taken per turn, not multiple.

💡 DP state must represent intervals, not counts of unlimited picks.

💡 Use dp[i][j] representing the best score difference for piles[i..j].

Why it failed: Fails by allowing multiple picks per turn (unbounded) leading to incorrect results. Fix by restricting picks to one pile per turn in DP.

✓ Correctly enforces one pick per turn and returns true.

t4_01performance

Input{"piles":[500,499,498,497,496,495,494,493,492,491,490,489,488,487,486,485,484,483,482,481,480,479,478,477,476,475,474,473,472,471,470,469,468,467,466,465,464,463,462,461,460,459,458,457,456,455,454,453,452,451,450,449,448,447,446,445,444,443,442,441,440,439,438,437,436,435,434,433,432,431,430,429,428,427,426,425,424,423,422,421,420,419,418,417,416,415,414,413,412,411,410,409,408,407,406,405,404,403,402,401]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(n^2) DP must complete within 2 seconds.

💡 Use bottom-up DP with O(n^2) time complexity.

💡 Avoid exponential recursion without memoization.

💡 Precompute sums or use memo to optimize repeated calculations.

Why it failed: TLE due to exponential brute force recursion without memoization. Fix by implementing O(n^2) DP with memo or tabulation.

✓ Efficient O(n^2) DP implementation confirmed.

Practice

1. Given the following code for finding the cheapest flight within K stops, what is the returned value for the input below? Input: n = 3 flights = [[0,1,100],[1,2,100],[0,2,500]] src = 0 dst = 2 K = 1

def findCheapestPrice(n, flights, src, dst, K):
    INF = float('inf')
    prev = [INF] * n
    prev[src] = 0
    for _ in range(K + 1):
        curr = prev[:]
        for u, v, w in flights:
            if prev[u] != INF:
                curr[v] = min(curr[v], prev[u] + w)
        prev = curr
    return prev[dst] if prev[dst] != INF else -1

print(findCheapestPrice(n, flights, src, dst, K))

easy

A. 500

B. 200

C. -1

D. 100

Solution

1. Step 1: Trace dp arrays for each iteration

   Initially prev = [0, inf, inf]. After first iteration (0 stops), curr updates cost to city 1 as 100 and city 2 as 500. After second iteration (1 stop), curr updates city 2 cost to min(500, 100 + 100) = 200.

2. Step 2: Return final cost for destination

   prev[2] after K+1=2 iterations is 200, which is the cheapest cost with at most 1 stop.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP updates costs correctly over K+1 iterations [OK]

Hint: DP updates cost over K+1 iterations [OK]

Common Mistakes:

• Returning direct edge cost ignoring stops
• Off-by-one in iteration count
• Confusing curr and prev arrays

2. Consider the following Python code implementing the space-optimized DP solution for Maximal Square. Given the input matrix below, what is the final returned value? Matrix: [ ["1", "0", "1"], ["1", "1", "1"], ["1", "1", "0"] ]

def maximalSquare(matrix):
    if not matrix or not matrix[0]:
        return 0
    rows, cols = len(matrix), len(matrix[0])
    dp = [0] * (cols + 1)
    max_side = 0
    prev = 0
    for i in range(rows):
        for j in range(1, cols + 1):
            temp = dp[j]
            if matrix[i][j-1] == '1':
                dp[j] = 1 + min(dp[j], dp[j-1], prev)
                max_side = max(max_side, dp[j])
            else:
                dp[j] = 0
            prev = temp
    return max_side * max_side

easy

A. 0

B. 4

C. 9

D. 1

Solution

1. Step 1: Trace dp array updates for each row

   Row 0: dp updates to [0,1,0,1], max_side=1; Row 1: dp updates to [0,1,1,1], then dp[3]=1+min(1,1,1)=2, max_side=2; Row 2: dp updates to [0,1,2,0], max_side remains 2.

2. Step 2: Calculate final area

   max_side=2, so area = 2*2 = 4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Max square side 2 -> area 4 [OK]

Hint: Track dp updates row-wise to find max side [OK]

Common Mistakes:

• Off-by-one in indexing dp array
• Confusing prev and temp updates
• Returning max_side instead of area

3. What is the time complexity of the bottom-up dynamic programming solution for the Burst Balloons problem with input size n, and why?

medium

A. O(n^3) because for each interval we try all possible last balloons to burst

B. O(n^3) due to three nested loops iterating over intervals and burst positions

C. O(2^n) because of the exponential number of burst orders

D. O(n^2) because we fill a 2D dp table of size n by n

Solution

1. Step 1: Identify loops in bottom-up DP

   There are three nested loops: length of interval (up to n), start index i (up to n), and position k (up to n) inside the interval.

2. Step 2: Calculate complexity

   Each loop runs up to n times, so total time is O(n * n * n) = O(n^3). The dp table is size O(n^2), but filling it requires the third loop over k.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Three nested loops over n -> O(n^3) time complexity [OK]

Hint: Three nested loops over intervals and positions cause cubic time [OK]

Common Mistakes:

• Confusing dp table size with time complexity
• Ignoring the innermost loop over k
• Assuming exponential time for DP solution

4. The following code attempts to compute the minimum falling path sum using bottom-up DP. Identify the line containing the subtle bug that causes incorrect results on some inputs.

def minFallingPathSum(matrix):
    n = len(matrix)
    dp = matrix[0][:]

    for i in range(1, n):
        for j in range(n):
            best = dp[j]
            if j > 0:
                best = min(best, dp[j-1])
            if j < n - 1:
                best = min(best, dp[j+1])
            dp[j] = matrix[i][j] + best

    return min(dp)

medium

A. Line 7: Updating dp[j] inside the inner loop without backup

B. Line 9: Checking if j > 0 before accessing dp[j-1]

C. Line 3: dp initialization with matrix[0][:]

D. Line 12: Returning min(dp) after the loops

Solution

1. Step 1: Understand dp update logic

   dp array holds minimum sums for previous row. Updating dp[j] in place overwrites values needed for neighbors in the same iteration.

2. Step 2: Identify the bug

   Updating dp[j] inside the inner loop without using a separate array causes premature overwriting, leading to incorrect neighbor comparisons.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Using a separate new_dp array fixes the bug [OK]

Hint: Don't overwrite dp while still reading from it in same iteration [OK]

Common Mistakes:

• Updating dp in place without backup
• Ignoring boundary checks

5. What is the time and space complexity of the optimal space-optimized bottom-up DP solution for the Unique Paths II problem on an m x n grid with obstacles?

medium

A. Time: O(m*n), Space: O(m*n)

B. Time: O(m+n), Space: O(m+n)

C. Time: O(m*n), Space: O(n)

D. Time: O(2^(m+n)), Space: O(m*n)

Solution

1. Step 1: Analyze time complexity

   The algorithm iterates over each cell once in nested loops: O(m*n).

2. Step 2: Analyze space complexity

   Uses a single 1D dp array of length n, so space is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Nested loops over m and n, dp array size n [OK]

Hint: Nested loops over m and n, dp array size n [OK]

Common Mistakes:

• Confusing recursion stack space with dp array
• Assuming full 2D dp array used
• Mistaking linear time for exponential