Burst Balloons

📋

Problem

Imagine you have a row of balloons, each with a number. Bursting a balloon earns coins equal to the product of the balloon's number and its adjacent balloons' numbers. How do you burst them all to maximize your coins?

Given n balloons, indexed from 0 to n-1, each with a positive integer number. When you burst balloon i, you earn coins equal to nums[left] * nums[i] * nums[right], where left and right are the adjacent balloons to i before bursting it. After bursting balloon i, it is removed, and the balloons left and right become adjacent. You want to find the maximum coins you can collect by bursting the balloons in an optimal order. Input: An array nums of integers representing balloon numbers. Output: An integer representing the maximum coins obtainable.

1 ≤ n ≤ 5001 ≤ nums[i] ≤ 100

Edge cases: Single balloon [5] → output 25All balloons have the same number [1,1,1] → output 4Increasing sequence [1,2,3,4] → output 40

</>

IDE

def maxCoins(nums: list[int]) -> int:public int maxCoins(int[] nums)int maxCoins(vector<int> &nums)function maxCoins(nums)

def maxCoins(nums):
    # Write your solution here
    pass

class Solution {
    public int maxCoins(int[] nums) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int maxCoins(vector<int> &nums) {
    // Write your solution here
    return 0;
}

function maxCoins(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 10100Greedy approach bursting largest balloon first, missing better interval bursting order.✅ Implement interval DP considering all possible last burst balloons in each interval.

Wrong: 0Not handling empty input or base cases properly.✅ Add base case: if nums is empty, return 0 immediately.

Wrong: less than expected (e.g. 2 for [1,1,1])Incorrect DP recurrence or missing intervals in calculation.✅ Ensure dp[left][right] considers all balloons i in (left, right) as last burst and sums subproblems correctly.

Wrong: greater than expected (e.g. >110 for [1,2,3,4,5])Treating problem as unbounded bursting (bursting balloons multiple times).✅ Use interval DP to ensure each balloon is burst exactly once.

Wrong: TLEUsing brute force exponential recursion without memoization or DP.✅ Implement top-down memoization or bottom-up DP with O(n^3) complexity.

✓

Test Cases

Make sure your solution handles base cases and small inputs correctly.

Focus on tricky cases that break greedy or naive approaches.

Optimize your DP to run efficiently on large inputs.

t1_01basic

Input{"nums":[3,1,5,8]}

Expected167

⏱ Performance - must finish in 2000ms

Optimal bursting order yields 167 coins. For example, bursting balloons in order 1, 5, 3, 8 yields coins: 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167.

💡 Think about bursting balloons in intervals and how coins accumulate.

💡 Use interval DP where dp[left][right] stores max coins between left and right balloons.

💡 Consider the last balloon to burst in each interval and combine subproblems.

Why it failed: Incorrect output means the DP recurrence or interval boundaries are wrong. Fix by ensuring dp[left][right] considers all possible last burst balloons i with coins = nums[left]*nums[i]*nums[right] + dp[left][i] + dp[i][right].

✓ Correctly implements interval DP with proper boundaries and recurrence.

t1_02basic

Input{"nums":[1,2,3,4]}

Expected40

⏱ Performance - must finish in 2000ms

Optimal bursting order yields 40 coins total.

💡 Try to think about the problem as bursting balloons from inside out.

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

💡 Remember to pad nums with 1 at both ends to simplify edge calculations.

Why it failed: If output is less than 40, likely missing some intervals or not considering all last burst balloons. Fix by iterating all i in (left, right) as last burst in dp.

✓ DP correctly computes max coins for all intervals.

t2_01edge

Input{"nums":[]}

Expected0

⏱ Performance - must finish in 2000ms

No balloons to burst, so max coins is 0.

💡 Check how your code handles empty input arrays.

💡 Make sure base cases return 0 when no balloons are present.

💡 Return 0 immediately if nums is empty or length zero.

Why it failed: Code crashes or returns non-zero for empty input. Fix by adding base case: if nums is empty, return 0.

✓ Handles empty input gracefully with zero coins.

t2_02edge

Input{"nums":[5]}

Expected5

⏱ Performance - must finish in 2000ms

Only one balloon, bursting it yields coins = 1*5*1 = 25 when considering padding balloons with 1 at both ends.

💡 Consider the padding of 1 at both ends for single balloon.

💡 DP intervals with length 1 should return 0, but bursting single balloon yields coins.

💡 Ensure your code handles intervals of length 2 correctly to burst the single balloon.

Why it failed: Output less than 25 means single balloon case not handled properly. Fix by correctly initializing dp for intervals with one balloon and padding with 1 at both ends.

✓ Correctly computes coins for single balloon input.

t2_03edge

Input{"nums":[1,1,1]}

Expected3

⏱ Performance - must finish in 2000ms

All balloons are 1, bursting any order yields total coins 4.

💡 Check if your DP handles identical balloon values correctly.

💡 Make sure all intervals are considered, not just greedy picks.

💡 Verify that coins calculation uses nums[left]*nums[i]*nums[right] correctly.

Why it failed: Output less than 4 means missing some intervals or incorrect multiplication. Fix by ensuring all subproblems are combined properly.

✓ Correctly handles identical balloon values.

t3_01corner

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

Expected20100

⏱ Performance - must finish in 2000ms

Bursting order: burst middle balloon first yields 100*1*100=10000 coins, then burst remaining balloons for total 20000.

💡 Beware of greedy approach that bursts largest balloon first.

💡 Use interval DP to consider all possible last burst balloons.

💡 Check that your DP tries bursting middle balloon first to maximize coins.

Why it failed: Greedy approach bursts largest balloon first and returns 10100 instead of 20000. Fix by implementing interval DP considering all last burst balloons.

✓ Correctly avoids greedy trap and finds max coins.

t3_02corner

Input{"nums":[1,2,3,2,1]}

Expected22

⏱ Performance - must finish in 2000ms

Complex sequence requiring full DP to find max coins 44.

💡 Check for off-by-one errors in interval boundaries.

💡 Ensure dp[left][right] excludes left and right balloons themselves.

💡 Verify recursion or iteration covers all subintervals.

Why it failed: Output less than 44 indicates off-by-one or incomplete interval coverage. Fix by correctly defining intervals and looping i in (left+1, right).

✓ Correctly handles intervals and boundaries.

t3_03corner

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

Expected110

⏱ Performance - must finish in 2000ms

Tests correct handling of 0/1 knapsack style confusion; must burst each balloon exactly once.

💡 Remember each balloon can be burst only once.

💡 Avoid treating problem as unbounded where balloons can be burst multiple times.

💡 Use DP intervals to ensure each balloon is counted once.

Why it failed: Output greater than 110 indicates unbounded bursting (counting balloons multiple times). Fix by using interval DP that ensures each balloon is burst once.

✓ Correctly enforces 0/1 bursting constraint.

t4_01performance

Input{"nums":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]}

Expectednull

⏱ Performance - must finish in 2000ms

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

💡 Brute force exponential solutions will time out here.

💡 Use bottom-up or top-down DP with memoization to achieve O(n^3).

💡 Optimize DP by careful indexing and pruning if possible.

Why it failed: TLE indicates exponential or inefficient solution. Fix by implementing O(n^3) DP with memoization or tabulation.

✓ Solution runs within time limit using O(n^3) DP.

Practice

1. Consider the following Python code implementing the Cherry Pickup problem using bottom-up DP. Given the input grid below, what is the final returned value?

grid = [
  [0, 1, -1],
  [1, 0, -1],
  [1, 1,  1]
]

from typing import List

def cherryPickup(grid: List[List[int]]) -> int:
    n = len(grid)
    dp = [[[-float('inf')] * n for _ in range(n)] for __ in range(n)]
    dp[0][0][0] = grid[0][0]
    for step in range(1, 2 * (n - 1) + 1):
        for r1 in range(max(0, step - (n - 1)), min(n, step + 1)):
            c1 = step - r1
            if c1 < 0 or c1 >= n:
                continue
            for r2 in range(max(0, step - (n - 1)), min(n, step + 1)):
                c2 = step - r2
                if c2 < 0 or c2 >= n:
                    continue
                if grid[r1][c1] == -1 or grid[r2][c2] == -1:
                    continue
                candidates = []
                if r1 > 0 and r2 > 0:
                    candidates.append(dp[r1 - 1][c1][r2 - 1])
                if r1 > 0 and c2 > 0:
                    candidates.append(dp[r1 - 1][c1][r2])
                if c1 > 0 and r2 > 0:
                    candidates.append(dp[r1][c1 - 1][r2 - 1])
                if c1 > 0 and c2 > 0:
                    candidates.append(dp[r1][c1 - 1][r2])
                best_prev = max(candidates) if candidates else -float('inf')
                if best_prev == -float('inf'):
                    continue
                val = best_prev + grid[r1][c1]
                if r1 != r2:
                    val += grid[r2][c2]
                dp[r1][c1][r2] = max(dp[r1][c1][r2], val)
    return max(0, dp[n - 1][n - 1][n - 1])

print(cherryPickup(grid))

easy

A. 6

B. 5

C. 4

D. 3

Solution

1. Step 1: Trace dp states for step=4 (final step for 3x3 grid)

   At step=4, both players reach bottom-right (2,2). The dp value dp[2][2][2] accumulates max cherries collected along valid paths avoiding thorns (-1).

2. Step 2: Calculate max cherries collected

   By tracing paths, max cherries collected is 6, considering both players' paths and avoiding double counting.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Manual path tracing confirms max cherries = 6 [OK]

Hint: Trace dp at final step for both players [OK]

Common Mistakes:

• Off-by-one errors in step or indices
• Double counting cherries when players overlap
• Ignoring thorn cells leading to invalid paths

2. You are given a 2D grid representing a dungeon where each cell contains an integer indicating health points gained or lost upon entering. You start at the top-left and must reach the bottom-right cell, moving only right or down. Your health must never drop below 1 at any point. Which algorithmic approach guarantees finding the minimum initial health required to survive the dungeon?

easy

A. Dynamic programming starting from the bottom-right cell and moving backward to the top-left

B. Greedy algorithm that always chooses the next cell with the highest health gain

C. Pure brute force recursion exploring all paths from start to end

D. Dijkstra's shortest path algorithm treating health as distance

Solution

1. Step 1: Understand problem constraints

   The problem requires minimum initial health ensuring health never drops below 1, which depends on future cells, so greedy or shortest path won't work.

2. Step 2: Identify correct DP direction

   Starting from the bottom-right cell and moving backward allows computing minimum health needed at each cell based on future states.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backward DP correctly accounts for future health requirements [OK]

Hint: Backward DP from goal ensures future states known [OK]

Common Mistakes:

• Assuming greedy or forward DP works
• Using shortest path ignoring health constraints

3. Consider the following buggy code for finding the cheapest flight within K stops. Which line contains the subtle bug that causes incorrect results on some inputs?

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

medium

A. Line 4: Initializing prev[src] = 0

B. Line 7: Checking if prev[u] != INF before relaxing edges

C. Line 6: Using prev array directly inside the loop instead of a separate curr array

D. Line 9: Returning -1 if prev[dst] is INF

Solution

1. Step 1: Understand the DP update mechanism

   In bottom-up DP, updates for the current iteration must not affect other relaxations in the same iteration, so a separate curr array is needed.

2. Step 2: Identify the bug

   Using prev directly causes updated costs to be used immediately in the same iteration, leading to incorrect minimum costs.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Separate curr array prevents premature updates [OK]

Hint: Must use separate curr array to avoid premature updates [OK]

Common Mistakes:

• Updating prev in-place during iteration
• Forgetting to copy arrays
• Ignoring stop constraints

4. The following code attempts to solve the Stone Game problem using bottom-up DP. Identify the line containing the subtle bug that causes incorrect results on some inputs.

def stoneGame(piles):
    n = len(piles)
    dp = [[0]*n for _ in range(n)]
    for i in range(n):
        dp[i][i] = piles[i]
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = max(piles[i] + dp[i+1][j], piles[j] + dp[i][j-1])
    return dp[0][n-1] > 0

medium

A. Line computing dp[i][j] = max(piles[i] + dp[i+1][j], piles[j] + dp[i][j-1])

B. Line initializing dp[i][i] = piles[i]

C. Line defining the outer loop for length in range(2, n+1)

D. Line returning dp[0][n-1] > 0

Solution

1. Step 1: Understand dp state meaning

   dp[i][j] should represent the maximum difference in stones the current player can achieve over the opponent.

2. Step 2: Identify incorrect recurrence

   The buggy line adds piles[i] + dp[i+1][j], which ignores the opponent's optimal response. The correct formula subtracts dp[i+1][j] to account for opponent's best play.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct recurrence uses subtraction, not addition [OK]

Hint: DP recurrence must subtract opponent's score [OK]

Common Mistakes:

• Adding dp values instead of subtracting opponent's score
• Forgetting base case initialization

5. Suppose the problem is modified so that you can reuse the same color for adjacent houses, but you want to minimize the total cost. Which modification to the DP solution is correct?

hard

A. Use brute force recursion without memoization since constraints are relaxed.

B. Keep excluding the previous color but add a penalty cost for same color adjacency.

C. Remove the condition excluding the previous color when computing min_prev; just take min(dp) for all colors.

D. Use a greedy approach picking the cheapest color for each house independently.

Solution

1. Step 1: Understand constraint relaxation

   Allowing same color for adjacent houses removes the need to exclude previous color in DP transitions.

2. Step 2: Modify DP accordingly

   Now min_prev is simply min(dp) over all colors, no exclusion needed. This simplifies the DP and still finds minimum cost.

3. Step 3: Evaluate other options

   Adding penalty is unnecessary. Brute force is inefficient. Greedy fails because costs vary per house and color.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Relaxed constraints allow including all colors in min calculation [OK]

Hint: Relaxed constraints mean no exclusion of previous color in DP [OK]

Common Mistakes:

• Still excluding previous color unnecessarily
• Adding penalty complicates solution
• Using brute force or greedy incorrectly