Definition
Burst Balloons uses interval DP on a padded array.
- Padding adds 1 at both ends so boundary multiplications are defined.
- dp[i][j] is the maximum coins from bursting all balloons strictly between i and j.
- Transition chooses k as the last balloon burst in (i, j): dp[i][j] = max over k of dp[i][k] + nums[i]*nums[k]*nums[j] + dp[k][j].
- Fill order iterates by increasing interval length so subintervals are ready.
- Time is O(n^3) and space is O(n^2).
A liquidation desk at National Bank of India closes positions one by one, where each closure's payout depends on its two surviving neighbors. The trick is to decide which position is closed LAST in a range, because then its neighbors are the fixed boundaries, splitting the range cleanly into two independent subranges.
Understanding the Concepts
What is the Burst Balloons Problem?
Given n balloons with values, bursting balloon i yields nums[left] * nums[i] * nums[right] coins, where left and right are the adjacent unburst balloons. Maximize the total coins from bursting all balloons.
At National Bank of India, a liquidation desk closes positions one by one, where each closure's payout depends on its two surviving neighbors. The order determines the total proceeds.
package com.bank.service;
public class BurstBalloons {
public static int maxCoins(int[] nums) {
int n = nums.length;
// Pad with 1 at both ends
int[] padded = new int[n + 2];
padded[0] = padded[n + 1] = 1;
for (int i = 0; i < n; i++) padded[i + 1] = nums[i];
int len = padded.length;
int[][] dp = new int[len][len];
// Fill by increasing interval length
for (int gap = 2; gap < len; gap++) {
for (int i = 0; i + gap < len; i++) {
int j = i + gap;
for (int k = i + 1; k < j; k++) {
int coins = dp[i][k] + padded[i] * padded[k] * padded[j] + dp[k][j];
dp[i][j] = Math.max(dp[i][j], coins);
}
}
}
return dp[0][n + 1];
}
public static void main(String[] args) {
int[] balloons = {3, 1, 5, 8};
System.out.println("Max coins: " + maxCoins(balloons));
}
}
Max coins: 167
Why Is Choosing the Last Balloon the Key Insight?
The difficulty is that bursting a balloon changes who its neighbors are. If we reason about which balloon to burst first, the two sides stay coupled because the first burst's neighbors keep shifting. The key insight is to flip the reasoning and pick which balloon is burst last in an interval.
When balloon k is the last to burst in the open interval (i, j), every other balloon in that interval is already gone. So k's neighbors are exactly the fixed boundaries i and j. This decouples the interval into two independent subranges: (i, k) and (k, j).
package com.bank.core;
public class LastBalloonInsight {
// Why LAST instead of FIRST?
// If k is burst FIRST in (i, j):
// k's neighbors are i and j initially
// BUT after bursting k, the balloons in (i,k) and (k,j) are now
// adjacent to each other, coupling the two sides
// If k is burst LAST in (i, j):
// All others are already gone
// k's neighbors are EXACTLY i and j (fixed boundaries)
// (i,k) and (k,j) are INDEPENDENT subproblems
}
How Does the Padding Work?
We pad the original array with 1 at both ends. This ensures that when a balloon at the boundary is burst last, its multiplication includes the boundary value of 1, which does not change the product. Without padding, we would need special cases for the first and last balloons.
package com.bank.core;
public class PaddingExplained {
public static void main(String[] args) {
int[] original = {3, 1, 5, 8};
int n = original.length;
int[] padded = new int[n + 2];
padded[0] = 1; // left boundary
padded[n + 1] = 1; // right boundary
for (int i = 0; i < n; i++) padded[i + 1] = original[i];
System.out.print("Padded: ");
for (int v : padded) System.out.print(v + " ");
// Output: 1 3 1 5 8 1
}
}
Padded: 1 3 1 5 8 1
How Does the Fill Order Work?
We fill by increasing interval length (gap between i and j). The smallest intervals (gap = 2, containing one balloon) are filled first. Larger intervals depend on smaller ones, so filling by increasing gap ensures all dependencies are ready.
package com.bank.core;
public class FillOrderTrace {
public static void main(String[] args) {
int[] padded = {1, 3, 1, 5, 8, 1};
int len = padded.length;
int[][] dp = new int[len][len];
for (int gap = 2; gap < len; gap++) {
System.out.println("Gap = " + gap + ":");
for (int i = 0; i + gap < len; i++) {
int j = i + gap;
for (int k = i + 1; k < j; k++) {
int coins = dp[i][k] + padded[i] * padded[k] * padded[j] + dp[k][j];
if (coins > dp[i][j]) {
dp[i][j] = coins;
System.out.println(" dp[" + i + "][" + j + "] = " + coins + " (last=" + k + ")");
}
}
}
}
System.out.println("Answer: " + dp[0][len - 1]);
}
}
Gap = 2:
dp[0][2] = 3 (last=1)
dp[1][3] = 15 (last=2)
dp[2][4] = 40 (last=3)
dp[3][5] = 40 (last=4)
Gap = 3:
dp[0][3] = 30 (last=2)
dp[1][4] = 135 (last=3)
dp[2][5] = 48 (last=3)
Gap = 4:
dp[0][4] = 159 (last=3)
dp[1][5] = 159 (last=3)
Gap = 5:
dp[0][5] = 167 (last=3)
Answer: 167
How Is This Similar to Matrix Chain Multiplication?
Both problems use the same "choose the last operation" reframing. In Matrix Chain Multiplication, you choose where to place the last multiplication split. In Burst Balloons, you choose which balloon to burst last. Both iterate by interval length, both have cubic time.
| Aspect | Burst Balloons | Matrix Chain Multiplication |
|---|---|---|
| Choice | Last balloon to burst | Last split point |
| Decoupling | Left and right subranges | Left and right matrix products |
| Boundaries | Padded values | Matrix dimensions |
| Time | O(n^3) | O(n^3) |
| Space | O(n^2) | O(n^2) |
// Both share the same skeleton:
// for (int gap = 2; gap < len; gap++)
// for (int i = 0; i + gap < len; i++)
// for (int k = i+1; k < j; k++)
// dp[i][j] = optimize(dp[i][k], cost(i,k,j), dp[k][j])
What Are the Edge Cases?
Edge cases include: a single balloon (just burst it, coins = the value since boundaries are both 1), two balloons (try both orders), and all balloons with value 1.
package com.bank.core;
public class BurstEdgeCases {
public static void main(String[] args) {
// Single balloon
System.out.println(BurstBalloons.maxCoins(new int[]{5})); // 5 (1*5*1)
// Two balloons
System.out.println(BurstBalloons.maxCoins(new int[]{3, 5}));
// Burst 3 first: 1*3*5 = 15, then 5: 1*5*1 = 5, total = 20
// Burst 5 first: 3*5*1 = 15, then 3: 1*3*1 = 3, total = 18
// Answer: 20
}
}
5
20
What About the Recursive Approach?
The recursive approach with memoization defines the same dp[i][j] but computes it top-down. This can be easier to implement but may hit stack limits for very large inputs.
package com.bank.core;
public class BurstRecursive {
private static int[][] memo;
private static int[] padded;
public static int maxCoins(int[] nums) {
int n = nums.length;
padded = new int[n + 2];
padded[0] = padded[n + 1] = 1;
for (int i = 0; i < n; i++) padded[i + 1] = nums[i];
memo = new int[n + 2][n + 2];
for (int[] row : memo) java.util.Arrays.fill(row, -1);
return solve(0, n + 1);
}
private static int solve(int i, int j) {
if (j - i < 2) return 0;
if (memo[i][j] != -1) return memo[i][j];
int best = 0;
for (int k = i + 1; k < j; k++) {
int coins = solve(i, k) + padded[i] * padded[k] * padded[j] + solve(k, j);
best = Math.max(best, coins);
}
memo[i][j] = best;
return best;
}
}
What Are Common Interview Follow-Up Questions?
Interviewers commonly ask:
- Matrix Chain Multiplication: same interval DP pattern, minimize multiplication cost.
- Minimum cost to merge stones: another interval DP with a group-size constraint.
- Why not choose the first balloon? Because it couples the two sides.
- Can you print the optimal burst order? Maintain a parallel
choicearray recording which k was chosen.
package com.bank.core;
public class BurstFollowUps {
// Matrix Chain: same skeleton, minimize cost
// Merge Stones: interval DP with group constraint
// Print order: track choice[i][j] = k, then reconstruct
}
Visual Overview
Burst Balloons Interval DP: Original: [3, 1, 5, 8] Padded: [1, 3, 1, 5, 8, 1] Indices: 0 1 2 3 4 5 dp[i][j] = max coins bursting all between i and j Choose k as LAST to burst in (i, j): ┌───────────────────────────────────────┐ │ dp[i][j] = max over k of: │ │ dp[i][k] │ │ + padded[i] * padded[k] * padded[j] │ │ + dp[k][j] │ │ │ │ k is last: neighbors are i and j │ │ (i,k) and (k,j) are independent │ └───────────────────────────────────────┘ Fill by increasing gap: gap=2: dp[0][2]=3, dp[1][3]=15, dp[2][4]=40, dp[3][5]=40 gap=3: dp[0][3]=30, dp[1][4]=135, dp[2][5]=48 gap=4: dp[0][4]=159, dp[1][5]=159 gap=5: dp[0][5]=167 <- ANSWER
Key Takeaway
Burst Balloons is a hard interval DP problem, and the whole difficulty is that bursting a balloon changes who its neighbors are. If I reason about which balloon to burst first, the two sides stay coupled because the first burst's neighbors keep shifting. The key insight is to flip the reasoning and pick which balloon is burst last within an interval.
When balloon k is the last to burst in the open interval between i and j, every other balloon in that interval is already gone, so k's neighbors are exactly the fixed boundaries i and j. That decouples the interval into two independent subranges. I pad the array with 1 at each end so the boundary multiplications are always defined.
The fill order iterates by increasing interval length, ensuring that when I compute dp[i][j], all shorter subintervals are already ready. The time is O(n^3) from three nested loops and the space is O(n^2). This "choose the last operation" reframing is the same signature trick behind matrix chain multiplication.
In my project at National Bank of India, a liquidation desk closed positions one at a time where each closure's payout depended on the two still-open neighbors. I used this interval DP to find the order that maximized total proceeds.
Remember one sentence: choose the last balloon to burst in each interval so its neighbors are the fixed boundaries, splitting the range into two independent subranges.
---