PPractick

The problem

You're designing the finale sequence for a fireworks show controlled by a game studio's physics engine. There are n balloons lined up in a row, each painted with a number representing its "coin value." When you burst a balloon, you collect left * current * right coins, where left and right are the values of the adjacent balloons at the time of bursting (not their original neighbors — once a balloon is burst, its former neighbors become adjacent to each other). If there's no balloon on one side (off the boundary), treat that side's value as 1. Your job: figure out the order to burst all balloons in to maximize total coins collected.

Example: nums = [3,1,5,8] — bursting in the right order gives 167 coins, achieved by bursting 1, then 5, then 3, then 8.

Function signature

int maxCoins(vector<int>& nums);

Test cases

Input nums	Output	Explanation
[3,1,5,8]	167	Burst order: 1→5→3→8 gives 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 15+120+24+8=167
[1,5]	10	Burst 1 first: 1*1*5=5, then burst 5: 1*5*1=5 → total 10
[]	0	No balloons, no coins
[7]	7	Single balloon: 1*7*1 = 7
[3,1,5]	35	Optimal order yields 35

(Constraints typically: n == nums.length, 0 <= n <= 300, 0 <= nums[i] <= 100)

How interviewers phrase it

• "Given an array representing balloon coin values, burst all balloons one at a time. Bursting a balloon gives you the product of its value and its current left/right neighbors. Maximize total coins."
• A strong hint they'll add: "Treat out-of-bounds balloons as having a value of 1."
• This is LeetCode 312, one of the most famous "hard" DP problems — interviewers use it specifically to test whether you can spot the "think about what's last, not what's first" trick, since the naive approach (decide which balloon to burst first) leads to a broken/non-overlapping subproblem structure.

Clarifying questions to ask

1. When a balloon is burst, do its neighbors permanently become adjacent for all future bursts, or does adjacency reset? (Confirm: yes, it's a real removal — left and right close the gap.)
2. What value do I use for "out of bounds" neighbors — is it always 1, or could it vary? (Standard: always 1.)
3. Can nums contain 0s? Does that change strategy? (Doesn't change the algorithm, but worth confirming since a 0-value balloon contributes nothing when burst directly but could still matter as a multiplier if burst at the wrong time — actually since it's a multiplier either way, 0s are handled naturally by the DP.)
4. What's the expected array size — n up to 300 suggests O(n³) DP is intended (300³ = 27M, feasible) rather than something more exotic.

Follow-ups to expect

1. "Why doesn't a 'burst first' greedy/DP approach work?"
2. "Can you reconstruct the actual burst order, not just the max coins?"
3. "What's the time and space complexity, and can you optimize space?"
4. "How is this related to Matrix Chain Multiplication?"
5. "What if you wanted to minimize the coins instead of maximize?"
6. "Can you do this without padding the array with 1s at the boundaries?"

Related questions

• Matrix chain multiplication Hard
• Matrix Chain Multiplication | Bottom-Up Hard
• Minimum cost to cut the stick Hard
• Palindrome partitioning II Hard
• Different Ways to Evaluate a Boolean Expression Medium
• Partition Array for Maximum Sum Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in