Leetcode 312. Burst Balloons
Given an array of balloon values, find the maximum coins you can collect by bursting balloons optimally. When you burst balloon at index i, you gain coins equal to nums[i-1] * nums[i] * nums[i+1] (treat out-of-bounds as 1). Return the maximum total coins obtainable. The reward depends on dynamic neighbors, so the core challenge is exploiting optimal substructure (interval/segment DP over subarrays) to find the best bursting sequence for n up to 300.
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Late August, 2026
You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons. If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it. Return the maximum coins you can collect by bursting the balloons wisely.
Late February, 2026
Late March, 2025
was asked the LC question without any variations
Hello Interview Premium
Your account is free and you can post anonymously if you choose.