← All questions
HardCoding

Burst balloons

Asked atSalesforce
1Give yourself 5 minutes
2Answer out loud, not in your head
3Then compare with the answer below

The problem

Given n balloons, indexed from 0 to n - 1, each balloon is painted with a number on it represented by an array nums. Burst all the balloons.

If the ith balloon is burst, the coins obtained are nums[i - 1] * nums[i] * nums[i + 1]. If i - 1 or i + 1 goes out of bounds of the array, treat it as if there is a balloon with a 1 painted on it.

Return the maximum coins that can be collected by bursting the balloons wisely.

Input : nums = [3, 1, 5, 8] Output : 167 Explanation : nums = [3, 1, 5, 8] --> [3, 5, 8] --> [3, 8] --> [8] --> [] coins = 315 + 358 + 138 + 181 = 167.

Input : nums = [1, 2, 3, 4] Output : 40 Explanation : nums = [1, 2, 3, 4] --> [1, 2, 4] --> [1, 4] --> [4] --> [] coins = 234 + 124 + 114 + 141 = 40.

Input : nums = [1, 5]

  • 1 <= n <= 300
  • 1 <= nums[i] <= 100

cpp

class Solution {
    public:
        int maxCoins(vector<int>& nums){
    	    //your code goes here
        }
};

java

class Solution {
    public int maxCoins(int[] nums) {
        //your code goes here
    }
}

python

class Solution:
    def maxCoins(self, nums):
        #your code goes here

javascript

class Solution {
    maxCoins(nums) {
        //your code goes here
    }
}

csharp

public class Solution
{
    public int MaxCoins(List<int> nums)
    {
        //your code goes here
    }
}

go

func maxCoins(nums []int) int {

}
Solve on LeetCode →
Stuck? Show a way to structure it+
  1. 01Pad nums with sentinel 1 values.
  2. 02Let dp[left][right] mean maximum coins for the open interval.
  3. 03Choose each index i as the last balloon burst.
  4. 04Combine independent left and right intervals.
  5. 05Fill intervals by increasing length.

Reference answer

Then expect these follow-ups

  • How would you recover one optimal burst order?

    Tests: follow-up reasoning

  • Why is last-burst reasoning cleaner than first-burst reasoning?

    Tests: correctness reasoning

Hiring now

Salesforce has 1,420 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

  • Business Development Representative Belgium Market (Dutch Speaking)

    Ireland - Dublin

  • Service Cloud Account Executive

    France - Paris

  • Summer Intern 2027 - Content Writer

    India - Bangalore

Or practice this question first

Next question