HardNo. 0312

Burst Balloons — LeetCode 312 Python Solution

Topics
Array, Dynamic Programming
On a study list
NeetCode 150
Reading time
2 min

The problem

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.

Example

Input
nums = [3,1,5,8]
Output
167
Explanation
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []

Python solution

PythonSolution
class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        n = len(nums)
        arr = [1] + nums + [1]
        f = [[0] * (n + 2) for _ in range(n + 2)]
        for i in range(n - 1, -1, -1):
            for j in range(i + 2, n + 2):
                for k in range(i + 1, j):
                    f[i][j] = max(f[i][j], f[i][k] + f[k][j] + arr[i] * arr[k] * arr[j])
        return f[0][-1]

Complexity

Time
O(n3)
Space · auxiliary
O(n2)

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 312. Burst Balloons is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0313Super Ugly NumberMedium
0309Best Time to Buy and Sell Stock with CooldownMedium
0322Coin ChangeMedium
0045Jump Game IIMedium
0053Maximum SubarrayMedium
0055Jump GameMedium

Frequently asked questions

How hard is LeetCode 312. Burst Balloons?

LeetCode 312. Burst Balloons is rated Hard on LeetCode.

What is the time complexity of LeetCode 312. Burst Balloons?

The Python solution on this page runs in O(n3).

What is the space complexity of LeetCode 312. Burst Balloons?

The Python solution on this page uses O(n2) auxiliary space.

What topics does LeetCode 312. Burst Balloons cover?

LeetCode 312. Burst Balloons is tagged Array and Dynamic Programming on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.