What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Dynamic Programming

Builds on Interval DP, which you haven’t finished yet.

P2HardBuilt on Interval DP~4 min speedrun

Burst Balloons (Choose the Last Item in a Range)

Built on

Interval DPEach range also chooses the last item handled inside it, and that choice splits the range into two independent halves.

The problem

Burst Balloons (LC 312)(opens leetcode.com)

Collect as many coins as you can by bursting every balloon in a row, one at a time, in an order you choose. The row holds n balloons, and nums[i] is the number written on balloon i (counting from 0).

A burst pays the product of three numbers: the burst balloon's own number and the numbers of its current left and right neighbours, meaning the closest balloons on each side that are still in the row. A side with no balloon left counts as 1.

Return the largest total any bursting order can reach.

Example 1

Input:nums = [3,1,5,8]

Output:167

One best order bursts the 1, then the 5, then the 3, then the 8: 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 15 + 120 + 24 + 8 = 167. The 8 goes last, so at that moment both of its neighbours are the phantom 1s.

Burst Balloons

row of items ➔ pick the last item handled in (i, j) ➔ dp over shorter intervals

Spot it when: Every item in a row (balloons, cuts on a stick, piles of stones, corners of a polygon) must be burst, cut or merged one at a time, the cost of each step depends on its neighbours or on the piece at that moment, and you want the best total over all orders.

Burst Balloons

Python

1	def max_coins(nums: list[int]) -> int:
2	"""Burst Balloons: interval DP that picks the LAST balloon to burst in each open range (i, j).
3	Time: O(N^3) \| Space: O(N^2)
4	"""
5	# vals: the row with phantom balloons worth 1 at both ends, standing for the missing edge neighbours
6	vals = [1] + nums + [1]
7	n = len(vals)
8	# dp: dp[i][j] is the most coins from bursting every balloon strictly between i and j
9	dp = [[0] * n for _ in range(n)]
10
11	# 1. Fill By Increasing Range Length:
12	# dp[i][j] reads dp[k][j] for k > i, a row further down the table, so every shorter range must
13	# be final first; looping by length, short ranges first, guarantees that order.
14	for length in range(2, n):
15	for i in range(n - length):
16	j = i + length
17	for k in range(i + 1, j):
18	# 2. Burst k Last In This Range:
19	# (i, k) and (k, j) are already empty when k bursts, so its only remaining neighbours
20	# are the walls vals[i] and vals[j]; k's two sides never touch, so their totals simply add.
21	coins = dp[i][k] + vals[i] * vals[k] * vals[j] + dp[k][j]
22	dp[i][j] = max(dp[i][j], coins)
23
24	return dp[0][n - 1]

Invariant: When dp[i][j] is computed, every shorter range is already final, and dp[i][j] becomes the most coins from bursting every balloon strictly between i and j while vals[i] and vals[j] still stand.

Let dp[i][j] be the most coins from bursting every balloon strictly between i and j, and try each k in range(i + 1, j) as the balloon that bursts LAST in that range: by then everything else between i and j is gone, so its neighbours are exactly the two walls vals[i] and vals[j], and it earns vals[i] * vals[k] * vals[j] whatever happened before. Because k stands until the end, it keeps the two sides apart: no balloon in (i, k) is ever next to one in (k, j), so each side is a smaller range of its own and their best totals dp[i][k] and dp[k][j] simply add. Choosing the FIRST balloon to burst splits nothing: once it is gone its two neighbours touch, and the coins on both sides depend on each other's order. The phantom 1s in vals = [1] + nums + [1] turn the whole row into one range, dp[0][n - 1]. The trap is the fill order: dp[i][j] reads dp[k][j] with k > i, a row further down the table, so fill by length, short ranges first (for length in range(2, n)); filling row by row from i = 0 reads dp[k][j] while it is still 0 and returns too few coins.

See it run

Burst Balloons on [3, 1, 5, 8], step by step

length 1

Rows are i and columns are j, written as index:vals[index]. The balloon k is the one that bursts last in the range (i, j).

write the range being written
dp[i][k] the range left of k
dp[k][j] the range right of k
answer the final result

vals = [1, 3, 1, 5, 8, 1], with an extra balloon worth 1 at each end. A range with no balloon inside is worth 0.

0:1

1:3

2:1

3:5

4:8

5:1

1 / 12

Gotchas1 of 4

The trap
Gotcha 1: Filling dp row by row from i = 0
Mistake
```
for i in range(n):
    for j in range(i + 2, n):
```
Fix
```
for length in range(2, n):
    for i in range(n - length):
        j = i + length
```
What happens: dp[i][j] reads dp[k][j] for every k > i, a row further down the table. A loop from i = 0 reads those cells while they are still 0. So the total is too small. Fill by length, short ranges first, or run i from n - 1 down to 0.
Example: nums = [3, 1, 5, 8]
Mistake: returns 63Fix: returns 167
Gotcha 2: Choosing k as the first balloon to burst
Mistake
```
coins = dp[i][k] + vals[k - 1] * vals[k] * vals[k + 1] + dp[k][j]
```
Fix
```
coins = dp[i][k] + vals[i] * vals[k] * vals[j] + dp[k][j]
```
What happens: vals[k - 1] and vals[k + 1] are the neighbours of k in the original row. Those balloons may burst before k, so the product is not what k earns. When k bursts last in (i, j), its neighbours are exactly vals[i] and vals[j].
Example: nums = [3, 1, 5, 8]
Mistake: returns 98Fix: returns 167
Gotcha 3: Padding vals with 0 instead of 1
Mistake
```
vals = [0] + nums + [0]
```
Fix
```
vals = [1] + nums + [1]
```
What happens: A balloon at the edge has a missing neighbour, and the problem counts it as worth 1. The two padded balloons stand for those missing neighbours. With 0, every burst next to an edge earns 0 coins.
Example: nums = [3, 1, 5, 8]
Mistake: returns 135Fix: returns 167
Gotcha 4: Leaving cuts unsorted before building marks
Mistake
```
marks = [0] + cuts + [n]
```
Fix
```
marks = [0] + sorted(cuts) + [n]
```
What happens: In Minimum Cost to Cut a Stick (LC 1547), the item to choose is the first cut made in a piece. That cut costs the whole piece, marks[j] - marks[i]. The ranges between marks are pieces only when marks is sorted. Unsorted cuts give wrong piece lengths.
Example: Minimum Cost to Cut a Stick (LC 1547): n = 9, cuts = [5, 6, 1, 4, 2]
Mistake: returns 2Fix: returns 22

Not this one if…

Two strings are matched prefix by prefix, as in Edit Distance (LC 72): each cell comes from the cell above, to the left or diagonal, and no item inside a range has to be chosen as the split. See Two-Sequence DP
A range is judged only by its own two ends, as in Longest Palindromic Substring (LC 5): nothing inside it is removed or chosen, so there is no split point to try. See Longest Palindromic Substring
The balloons are ranges on a line and one arrow bursts every range it crosses, as in Minimum Number of Arrows to Burst Balloons (LC 452): no cost depends on what was removed before, so the order of removal never matters. See Interval Scheduling

Deep Dive

What this card adds to Interval DP

Interval DP already gives the state: one answer dp[i][j] for a range, built from shorter ranges and filled by increasing length. This card adds one more choice inside each range. It picks the balloon k that bursts last, and that choice splits the range into two independent parts.

dp[i][j] is the most coins from bursting every balloon strictly between positions i and j. The balloons at i and j are not burst. They are two fixed end balloons for the whole range.

In vals = [1] + nums + [1], the two extra balloons worth 1 stand for the missing neighbours at the two ends. Then the whole problem is the single range dp[0][n - 1].

Example: for nums = [3, 1, 5, 8], vals is [1, 3, 1, 5, 8, 1]. In that array, dp[1][4] is 135. It is the best result for bursting the balloons worth 1 and 5, with the end balloons 3 and 8 standing.

Why the last balloon splits the range

Try each k in range(i + 1, j) as the balloon that bursts last in the range. Before k bursts, every other balloon between i and j is already gone. So the neighbours of k are the two walls, and it earns vals[i] * vals[k] * vals[j].

Because k is still standing, it separates the two sides. A balloon in (i, k) never has a neighbour in (k, j). So the two sides are independent ranges. Their best totals dp[i][k] and dp[k][j] do not affect each other, and they are added.

Choosing the first balloon to burst does not work, because it splits nothing. After it bursts, its two neighbours become next to each other. The coins on one side then depend on the order on the other side, so there are no independent parts.

Example: in the range (0, 5) of [1, 3, 1, 5, 8, 1], k = 4 gives 159 + 1 * 8 * 1 + 0 = 167, and k = 1 gives only 162. The maximum over all k is 167.

Why the fill order is by length

dp[i][j] reads dp[i][k] and dp[k][j]. Both are ranges that are shorter than j - i. So every shorter range must be final before the longer one is computed.

The loop for length in range(2, n) fills ranges of length 2 first, then 3, and so on. The smallest range with a balloon inside has length 2, and its value is vals[i] * vals[i + 1] * vals[i + 2].

A loop that goes row by row from i = 0 reads dp[k][j] for k > i, a row that has not been filled yet. It reads 0, and the total is too small. For [3, 1, 5, 8] it returns 63 instead of 167.

The cost: ranges times split points

The card's complexity line is O(N^3) time and O(N^2) space. There are about n^2 / 2 ranges (i, j), and each tries up to n values of k.

For 100 balloons, vals has 102 entries. The loops run 171,700 times through the line that computes coins. The table dp has 102 * 102 = 10,404 cells.

Other problems use the same shape. In Minimum Cost to Cut a Stick (LC 1547), marks = [0] + sorted(cuts) + [n] is the row, and the chosen k is the first cut in a piece. It costs marks[j] - marks[i], then the two sides are solved separately. For n = 7 and cuts = [1, 3, 4, 5] the answer is 16.

60-Second Pitch

"Trying every order of bursting is N factorial. I switch the question: in a range, which balloon bursts last? If k bursts last in the range (i, j), all others are gone, so its neighbours are vals[i] and vals[j]. It earns vals[i] * vals[k] * vals[j]. The left and right sides are independent ranges, so I add dp[i][k] and dp[k][j]. I pad the row with two 1s, so the whole problem is dp[0][n - 1]. I fill by increasing range length, so shorter ranges are final first. There are about N squared ranges and N split points each. That is O(N^3) time and O(N^2) space."

Common Questions

Why do we choose the last balloon and not the first?: The last balloon is still standing while everything else in the range bursts. So its neighbours are known (the walls), and it separates the range into two independent sides. The first balloon makes its two neighbours touch, and the sides depend on each other.
What is the time and space complexity, and why?: O(N^3) time and O(N^2) space. There are about N^2 / 2 ranges (i, j), and each range tries up to N values of k. The table dp has (N + 2)^2 cells.
Can you fill the table in another order?: Yes. Run i from n - 1 down to 0, and j from i + 2 up to n - 1. Then dp[k][j] for k > i is already final. Any order works if the two smaller ranges (i, k) and (k, j) are computed before (i, j).
How does Minimum Cost to Cut a Stick (LC 1547) fit the same template?: Use marks = [0] + sorted(cuts) + [n]. For a piece (i, j), try each mark k between them as the first cut. That cut costs marks[j] - marks[i], and the two new pieces are solved independently. Take the minimum. For n = 7 and cuts = [1, 3, 4, 5] the answer is 16.
Can this be solved with memoization?: Yes. Write solve(i, j) with a cache keyed by (i, j), and call it for (0, n - 1). It computes the same recurrence and visits only reachable ranges. The depth is at most N, and the time is still O(N^3).

SWE Reasoning

Spot it

Items in a row are removed, cut or merged one at a time, and you want the best total over all orders.
The cost of a step depends on the neighbours or on the piece at that moment, not on the item alone.
The number of orders is N!, but the problem has a natural sub-problem: a continuous range of the row.
If you fix the item that is handled last in a range, the rest splits into a left part and a right part that do not touch.
N is small, often 100 to 500 items. This allows O(N^3).

The invariant, step by step

Pad the row: vals = [1] + nums + [1]. Set n = len(vals). Create dp with n rows and n columns, all 0.
The loop sets length to 2, then 3, up to n - 1. Every range of the previous lengths is already final.
For a range (i, j), the code tries each k between them as the balloon that bursts last.
When k bursts last, everything else in the range is gone. Its neighbours are vals[i] and vals[j], so it earns vals[i] * vals[k] * vals[j].
The two sides (i, k) and (k, j) never touch, because k stands until the end. Their totals dp[i][k] and dp[k][j] are final and are added.
dp[i][j] keeps the maximum over all k. At the end, dp[0][n - 1] is the best result for the whole row.

Traps

Wrong fill order. Filling row by row from i = 0 reads cells that are still 0. For [3, 1, 5, 8] it returns 63 instead of 167.
Picking the first balloon. Using vals[k - 1] * vals[k] * vals[k + 1] assumes the original neighbours are still there. For [3, 1, 5, 8] it returns 98 instead of 167.
Padding with 0. The missing neighbour counts as 1. With 0, every burst next to an edge earns 0, and the result is 135 for [3, 1, 5, 8].
Unsorted cuts. In Minimum Cost to Cut a Stick (LC 1547), ranges between marks are pieces only if marks is sorted. For n = 9 and cuts = [5, 6, 1, 4, 2], unsorted marks return 2 instead of 22.
Range ends inside the range. If k can equal i or j, the balloon is a wall and is not burst. Use range(i + 1, j).

Practice

Canonical LeetCode:Burst Balloons (LC 312)Minimum Cost to Cut a Stick (LC 1547)Minimum Score Triangulation of Polygon (LC 1039)Minimum Cost to Merge Stones (LC 1000)Guess Number Higher or Lower II (LC 375)

Theory Context•Dynamic Programming

Builds on Interval DP, which you haven’t finished yet.

P2HardBuilt on Interval DP~4 min speedrun

Burst Balloons (Choose the Last Item in a Range)

Built on

Interval DPEach range also chooses the last item handled inside it, and that choice splits the range into two independent halves.

The problem

Burst Balloons (LC 312)(opens leetcode.com)

Return the largest total any bursting order can reach.

Example 1

Input:nums = [3,1,5,8]

Output:167

Burst Balloons

row of items ➔ pick the last item handled in (i, j) ➔ dp over shorter intervals

Burst Balloons

Python

1	def max_coins(nums: list[int]) -> int:
2	"""Burst Balloons: interval DP that picks the LAST balloon to burst in each open range (i, j).
3	Time: O(N^3) \| Space: O(N^2)
4	"""
5	# vals: the row with phantom balloons worth 1 at both ends, standing for the missing edge neighbours
6	vals = [1] + nums + [1]
7	n = len(vals)
8	# dp: dp[i][j] is the most coins from bursting every balloon strictly between i and j
9	dp = [[0] * n for _ in range(n)]
10
11	# 1. Fill By Increasing Range Length:
12	# dp[i][j] reads dp[k][j] for k > i, a row further down the table, so every shorter range must
13	# be final first; looping by length, short ranges first, guarantees that order.
14	for length in range(2, n):
15	for i in range(n - length):
16	j = i + length
17	for k in range(i + 1, j):
18	# 2. Burst k Last In This Range:
19	# (i, k) and (k, j) are already empty when k bursts, so its only remaining neighbours
20	# are the walls vals[i] and vals[j]; k's two sides never touch, so their totals simply add.
21	coins = dp[i][k] + vals[i] * vals[k] * vals[j] + dp[k][j]
22	dp[i][j] = max(dp[i][j], coins)
23
24	return dp[0][n - 1]

See it run

Burst Balloons on [3, 1, 5, 8], step by step

length 1

Rows are i and columns are j, written as index:vals[index]. The balloon k is the one that bursts last in the range (i, j).

write the range being written
dp[i][k] the range left of k
dp[k][j] the range right of k
answer the final result

vals = [1, 3, 1, 5, 8, 1], with an extra balloon worth 1 at each end. A range with no balloon inside is worth 0.

0:1

1:3

2:1

3:5

4:8

5:1

1 / 12

Gotchas1 of 4

The trap
Gotcha 1: Filling dp row by row from i = 0
Mistake
```
for i in range(n):
    for j in range(i + 2, n):
```
Fix
```
for length in range(2, n):
    for i in range(n - length):
        j = i + length
```
What happens: dp[i][j] reads dp[k][j] for every k > i, a row further down the table. A loop from i = 0 reads those cells while they are still 0. So the total is too small. Fill by length, short ranges first, or run i from n - 1 down to 0.
Example: nums = [3, 1, 5, 8]
Mistake: returns 63Fix: returns 167
Gotcha 2: Choosing k as the first balloon to burst
Mistake
```
coins = dp[i][k] + vals[k - 1] * vals[k] * vals[k + 1] + dp[k][j]
```
Fix
```
coins = dp[i][k] + vals[i] * vals[k] * vals[j] + dp[k][j]
```
What happens: vals[k - 1] and vals[k + 1] are the neighbours of k in the original row. Those balloons may burst before k, so the product is not what k earns. When k bursts last in (i, j), its neighbours are exactly vals[i] and vals[j].
Example: nums = [3, 1, 5, 8]
Mistake: returns 98Fix: returns 167
Gotcha 3: Padding vals with 0 instead of 1
Mistake
```
vals = [0] + nums + [0]
```
Fix
```
vals = [1] + nums + [1]
```
What happens: A balloon at the edge has a missing neighbour, and the problem counts it as worth 1. The two padded balloons stand for those missing neighbours. With 0, every burst next to an edge earns 0 coins.
Example: nums = [3, 1, 5, 8]
Mistake: returns 135Fix: returns 167
Gotcha 4: Leaving cuts unsorted before building marks
Mistake
```
marks = [0] + cuts + [n]
```
Fix
```
marks = [0] + sorted(cuts) + [n]
```
What happens: In Minimum Cost to Cut a Stick (LC 1547), the item to choose is the first cut made in a piece. That cut costs the whole piece, marks[j] - marks[i]. The ranges between marks are pieces only when marks is sorted. Unsorted cuts give wrong piece lengths.
Example: Minimum Cost to Cut a Stick (LC 1547): n = 9, cuts = [5, 6, 1, 4, 2]
Mistake: returns 2Fix: returns 22

Not this one if…

Two strings are matched prefix by prefix, as in Edit Distance (LC 72): each cell comes from the cell above, to the left or diagonal, and no item inside a range has to be chosen as the split. See Two-Sequence DP
A range is judged only by its own two ends, as in Longest Palindromic Substring (LC 5): nothing inside it is removed or chosen, so there is no split point to try. See Longest Palindromic Substring
The balloons are ranges on a line and one arrow bursts every range it crosses, as in Minimum Number of Arrows to Burst Balloons (LC 452): no cost depends on what was removed before, so the order of removal never matters. See Interval Scheduling

Deep Dive

What this card adds to Interval DP

dp[i][j] is the most coins from bursting every balloon strictly between positions i and j. The balloons at i and j are not burst. They are two fixed end balloons for the whole range.

In vals = [1] + nums + [1], the two extra balloons worth 1 stand for the missing neighbours at the two ends. Then the whole problem is the single range dp[0][n - 1].

Why the last balloon splits the range

Example: in the range (0, 5) of [1, 3, 1, 5, 8, 1], k = 4 gives 159 + 1 * 8 * 1 + 0 = 167, and k = 1 gives only 162. The maximum over all k is 167.

Why the fill order is by length

dp[i][j] reads dp[i][k] and dp[k][j]. Both are ranges that are shorter than j - i. So every shorter range must be final before the longer one is computed.

The loop for length in range(2, n) fills ranges of length 2 first, then 3, and so on. The smallest range with a balloon inside has length 2, and its value is vals[i] * vals[i + 1] * vals[i + 2].

A loop that goes row by row from i = 0 reads dp[k][j] for k > i, a row that has not been filled yet. It reads 0, and the total is too small. For [3, 1, 5, 8] it returns 63 instead of 167.

The cost: ranges times split points

The card's complexity line is O(N^3) time and O(N^2) space. There are about n^2 / 2 ranges (i, j), and each tries up to n values of k.

For 100 balloons, vals has 102 entries. The loops run 171,700 times through the line that computes coins. The table dp has 102 * 102 = 10,404 cells.

60-Second Pitch

Common Questions

Why do we choose the last balloon and not the first?: The last balloon is still standing while everything else in the range bursts. So its neighbours are known (the walls), and it separates the range into two independent sides. The first balloon makes its two neighbours touch, and the sides depend on each other.
What is the time and space complexity, and why?: O(N^3) time and O(N^2) space. There are about N^2 / 2 ranges (i, j), and each range tries up to N values of k. The table dp has (N + 2)^2 cells.
Can you fill the table in another order?: Yes. Run i from n - 1 down to 0, and j from i + 2 up to n - 1. Then dp[k][j] for k > i is already final. Any order works if the two smaller ranges (i, k) and (k, j) are computed before (i, j).
How does Minimum Cost to Cut a Stick (LC 1547) fit the same template?: Use marks = [0] + sorted(cuts) + [n]. For a piece (i, j), try each mark k between them as the first cut. That cut costs marks[j] - marks[i], and the two new pieces are solved independently. Take the minimum. For n = 7 and cuts = [1, 3, 4, 5] the answer is 16.
Can this be solved with memoization?: Yes. Write solve(i, j) with a cache keyed by (i, j), and call it for (0, n - 1). It computes the same recurrence and visits only reachable ranges. The depth is at most N, and the time is still O(N^3).

SWE Reasoning

Spot it

Items in a row are removed, cut or merged one at a time, and you want the best total over all orders.
The cost of a step depends on the neighbours or on the piece at that moment, not on the item alone.
The number of orders is N!, but the problem has a natural sub-problem: a continuous range of the row.
If you fix the item that is handled last in a range, the rest splits into a left part and a right part that do not touch.
N is small, often 100 to 500 items. This allows O(N^3).

The invariant, step by step

Pad the row: vals = [1] + nums + [1]. Set n = len(vals). Create dp with n rows and n columns, all 0.
The loop sets length to 2, then 3, up to n - 1. Every range of the previous lengths is already final.
For a range (i, j), the code tries each k between them as the balloon that bursts last.
When k bursts last, everything else in the range is gone. Its neighbours are vals[i] and vals[j], so it earns vals[i] * vals[k] * vals[j].
The two sides (i, k) and (k, j) never touch, because k stands until the end. Their totals dp[i][k] and dp[k][j] are final and are added.
dp[i][j] keeps the maximum over all k. At the end, dp[0][n - 1] is the best result for the whole row.

Traps

Wrong fill order. Filling row by row from i = 0 reads cells that are still 0. For [3, 1, 5, 8] it returns 63 instead of 167.
Picking the first balloon. Using vals[k - 1] * vals[k] * vals[k + 1] assumes the original neighbours are still there. For [3, 1, 5, 8] it returns 98 instead of 167.
Padding with 0. The missing neighbour counts as 1. With 0, every burst next to an edge earns 0, and the result is 135 for [3, 1, 5, 8].
Unsorted cuts. In Minimum Cost to Cut a Stick (LC 1547), ranges between marks are pieces only if marks is sorted. For n = 9 and cuts = [5, 6, 1, 4, 2], unsorted marks return 2 instead of 22.
Range ends inside the range. If k can equal i or j, the balloon is a wall and is not burst. Use range(i + 1, j).

Practice

Theory Context•Dynamic Programming

Builds on Interval DP, which you haven’t finished yet.

P2HardBuilt on Interval DP~4 min speedrun

Burst Balloons (Choose the Last Item in a Range)

Built on

Interval DPEach range also chooses the last item handled inside it, and that choice splits the range into two independent halves.

The problem

Burst Balloons (LC 312)(opens leetcode.com)

Return the largest total any bursting order can reach.

Example 1

Input:nums = [3,1,5,8]

Output:167

Burst Balloons

row of items ➔ pick the last item handled in (i, j) ➔ dp over shorter intervals

Burst Balloons

Python

1	def max_coins(nums: list[int]) -> int:
2	"""Burst Balloons: interval DP that picks the LAST balloon to burst in each open range (i, j).
3	Time: O(N^3) \| Space: O(N^2)
4	"""
5	# vals: the row with phantom balloons worth 1 at both ends, standing for the missing edge neighbours
6	vals = [1] + nums + [1]
7	n = len(vals)
8	# dp: dp[i][j] is the most coins from bursting every balloon strictly between i and j
9	dp = [[0] * n for _ in range(n)]
10
11	# 1. Fill By Increasing Range Length:
12	# dp[i][j] reads dp[k][j] for k > i, a row further down the table, so every shorter range must
13	# be final first; looping by length, short ranges first, guarantees that order.
14	for length in range(2, n):
15	for i in range(n - length):
16	j = i + length
17	for k in range(i + 1, j):
18	# 2. Burst k Last In This Range:
19	# (i, k) and (k, j) are already empty when k bursts, so its only remaining neighbours
20	# are the walls vals[i] and vals[j]; k's two sides never touch, so their totals simply add.
21	coins = dp[i][k] + vals[i] * vals[k] * vals[j] + dp[k][j]
22	dp[i][j] = max(dp[i][j], coins)
23
24	return dp[0][n - 1]

See it run

Burst Balloons on [3, 1, 5, 8], step by step

length 1

Rows are i and columns are j, written as index:vals[index]. The balloon k is the one that bursts last in the range (i, j).

write the range being written
dp[i][k] the range left of k
dp[k][j] the range right of k
answer the final result

vals = [1, 3, 1, 5, 8, 1], with an extra balloon worth 1 at each end. A range with no balloon inside is worth 0.

0:1

1:3

2:1

3:5

4:8

5:1

1 / 12

Gotchas1 of 4

The trap
Gotcha 1: Filling dp row by row from i = 0
Mistake
```
for i in range(n):
    for j in range(i + 2, n):
```
Fix
```
for length in range(2, n):
    for i in range(n - length):
        j = i + length
```
What happens: dp[i][j] reads dp[k][j] for every k > i, a row further down the table. A loop from i = 0 reads those cells while they are still 0. So the total is too small. Fill by length, short ranges first, or run i from n - 1 down to 0.
Example: nums = [3, 1, 5, 8]
Mistake: returns 63Fix: returns 167
Gotcha 2: Choosing k as the first balloon to burst
Mistake
```
coins = dp[i][k] + vals[k - 1] * vals[k] * vals[k + 1] + dp[k][j]
```
Fix
```
coins = dp[i][k] + vals[i] * vals[k] * vals[j] + dp[k][j]
```
What happens: vals[k - 1] and vals[k + 1] are the neighbours of k in the original row. Those balloons may burst before k, so the product is not what k earns. When k bursts last in (i, j), its neighbours are exactly vals[i] and vals[j].
Example: nums = [3, 1, 5, 8]
Mistake: returns 98Fix: returns 167
Gotcha 3: Padding vals with 0 instead of 1
Mistake
```
vals = [0] + nums + [0]
```
Fix
```
vals = [1] + nums + [1]
```
What happens: A balloon at the edge has a missing neighbour, and the problem counts it as worth 1. The two padded balloons stand for those missing neighbours. With 0, every burst next to an edge earns 0 coins.
Example: nums = [3, 1, 5, 8]
Mistake: returns 135Fix: returns 167
Gotcha 4: Leaving cuts unsorted before building marks
Mistake
```
marks = [0] + cuts + [n]
```
Fix
```
marks = [0] + sorted(cuts) + [n]
```
What happens: In Minimum Cost to Cut a Stick (LC 1547), the item to choose is the first cut made in a piece. That cut costs the whole piece, marks[j] - marks[i]. The ranges between marks are pieces only when marks is sorted. Unsorted cuts give wrong piece lengths.
Example: Minimum Cost to Cut a Stick (LC 1547): n = 9, cuts = [5, 6, 1, 4, 2]
Mistake: returns 2Fix: returns 22

Not this one if…

Two strings are matched prefix by prefix, as in Edit Distance (LC 72): each cell comes from the cell above, to the left or diagonal, and no item inside a range has to be chosen as the split. See Two-Sequence DP
A range is judged only by its own two ends, as in Longest Palindromic Substring (LC 5): nothing inside it is removed or chosen, so there is no split point to try. See Longest Palindromic Substring
The balloons are ranges on a line and one arrow bursts every range it crosses, as in Minimum Number of Arrows to Burst Balloons (LC 452): no cost depends on what was removed before, so the order of removal never matters. See Interval Scheduling

Deep Dive

What this card adds to Interval DP

dp[i][j] is the most coins from bursting every balloon strictly between positions i and j. The balloons at i and j are not burst. They are two fixed end balloons for the whole range.

In vals = [1] + nums + [1], the two extra balloons worth 1 stand for the missing neighbours at the two ends. Then the whole problem is the single range dp[0][n - 1].

Why the last balloon splits the range

Example: in the range (0, 5) of [1, 3, 1, 5, 8, 1], k = 4 gives 159 + 1 * 8 * 1 + 0 = 167, and k = 1 gives only 162. The maximum over all k is 167.

Why the fill order is by length

dp[i][j] reads dp[i][k] and dp[k][j]. Both are ranges that are shorter than j - i. So every shorter range must be final before the longer one is computed.

The loop for length in range(2, n) fills ranges of length 2 first, then 3, and so on. The smallest range with a balloon inside has length 2, and its value is vals[i] * vals[i + 1] * vals[i + 2].

A loop that goes row by row from i = 0 reads dp[k][j] for k > i, a row that has not been filled yet. It reads 0, and the total is too small. For [3, 1, 5, 8] it returns 63 instead of 167.

The cost: ranges times split points

The card's complexity line is O(N^3) time and O(N^2) space. There are about n^2 / 2 ranges (i, j), and each tries up to n values of k.

For 100 balloons, vals has 102 entries. The loops run 171,700 times through the line that computes coins. The table dp has 102 * 102 = 10,404 cells.

60-Second Pitch

Common Questions

Why do we choose the last balloon and not the first?: The last balloon is still standing while everything else in the range bursts. So its neighbours are known (the walls), and it separates the range into two independent sides. The first balloon makes its two neighbours touch, and the sides depend on each other.
What is the time and space complexity, and why?: O(N^3) time and O(N^2) space. There are about N^2 / 2 ranges (i, j), and each range tries up to N values of k. The table dp has (N + 2)^2 cells.
Can you fill the table in another order?: Yes. Run i from n - 1 down to 0, and j from i + 2 up to n - 1. Then dp[k][j] for k > i is already final. Any order works if the two smaller ranges (i, k) and (k, j) are computed before (i, j).
How does Minimum Cost to Cut a Stick (LC 1547) fit the same template?: Use marks = [0] + sorted(cuts) + [n]. For a piece (i, j), try each mark k between them as the first cut. That cut costs marks[j] - marks[i], and the two new pieces are solved independently. Take the minimum. For n = 7 and cuts = [1, 3, 4, 5] the answer is 16.
Can this be solved with memoization?: Yes. Write solve(i, j) with a cache keyed by (i, j), and call it for (0, n - 1). It computes the same recurrence and visits only reachable ranges. The depth is at most N, and the time is still O(N^3).

SWE Reasoning

Spot it

Items in a row are removed, cut or merged one at a time, and you want the best total over all orders.
The cost of a step depends on the neighbours or on the piece at that moment, not on the item alone.
The number of orders is N!, but the problem has a natural sub-problem: a continuous range of the row.
If you fix the item that is handled last in a range, the rest splits into a left part and a right part that do not touch.
N is small, often 100 to 500 items. This allows O(N^3).

The invariant, step by step

Pad the row: vals = [1] + nums + [1]. Set n = len(vals). Create dp with n rows and n columns, all 0.
The loop sets length to 2, then 3, up to n - 1. Every range of the previous lengths is already final.
For a range (i, j), the code tries each k between them as the balloon that bursts last.
When k bursts last, everything else in the range is gone. Its neighbours are vals[i] and vals[j], so it earns vals[i] * vals[k] * vals[j].
The two sides (i, k) and (k, j) never touch, because k stands until the end. Their totals dp[i][k] and dp[k][j] are final and are added.
dp[i][j] keeps the maximum over all k. At the end, dp[0][n - 1] is the best result for the whole row.

Traps

Wrong fill order. Filling row by row from i = 0 reads cells that are still 0. For [3, 1, 5, 8] it returns 63 instead of 167.
Picking the first balloon. Using vals[k - 1] * vals[k] * vals[k + 1] assumes the original neighbours are still there. For [3, 1, 5, 8] it returns 98 instead of 167.
Padding with 0. The missing neighbour counts as 1. With 0, every burst next to an edge earns 0, and the result is 135 for [3, 1, 5, 8].
Unsorted cuts. In Minimum Cost to Cut a Stick (LC 1547), ranges between marks are pieces only if marks is sorted. For n = 9 and cuts = [5, 6, 1, 4, 2], unsorted marks return 2 instead of 22.
Range ends inside the range. If k can equal i or j, the balloon is a wall and is not burst. Use range(i + 1, j).

Practice

Theory Context•Dynamic Programming

Builds on Interval DP, which you haven’t finished yet.

P2HardBuilt on Interval DP~4 min speedrun

Burst Balloons (Choose the Last Item in a Range)

Built on

Interval DPEach range also chooses the last item handled inside it, and that choice splits the range into two independent halves.

The problem

Burst Balloons (LC 312)(opens leetcode.com)

Return the largest total any bursting order can reach.

Example 1

Input:nums = [3,1,5,8]

Output:167

Burst Balloons

row of items ➔ pick the last item handled in (i, j) ➔ dp over shorter intervals

Burst Balloons

Python

1	def max_coins(nums: list[int]) -> int:
2	"""Burst Balloons: interval DP that picks the LAST balloon to burst in each open range (i, j).
3	Time: O(N^3) \| Space: O(N^2)
4	"""
5	# vals: the row with phantom balloons worth 1 at both ends, standing for the missing edge neighbours
6	vals = [1] + nums + [1]
7	n = len(vals)
8	# dp: dp[i][j] is the most coins from bursting every balloon strictly between i and j
9	dp = [[0] * n for _ in range(n)]
10
11	# 1. Fill By Increasing Range Length:
12	# dp[i][j] reads dp[k][j] for k > i, a row further down the table, so every shorter range must
13	# be final first; looping by length, short ranges first, guarantees that order.
14	for length in range(2, n):
15	for i in range(n - length):
16	j = i + length
17	for k in range(i + 1, j):
18	# 2. Burst k Last In This Range:
19	# (i, k) and (k, j) are already empty when k bursts, so its only remaining neighbours
20	# are the walls vals[i] and vals[j]; k's two sides never touch, so their totals simply add.
21	coins = dp[i][k] + vals[i] * vals[k] * vals[j] + dp[k][j]
22	dp[i][j] = max(dp[i][j], coins)
23
24	return dp[0][n - 1]

See it run

Burst Balloons on [3, 1, 5, 8], step by step

length 1

Rows are i and columns are j, written as index:vals[index]. The balloon k is the one that bursts last in the range (i, j).

write the range being written
dp[i][k] the range left of k
dp[k][j] the range right of k
answer the final result

vals = [1, 3, 1, 5, 8, 1], with an extra balloon worth 1 at each end. A range with no balloon inside is worth 0.

0:1

1:3

2:1

3:5

4:8

5:1

1 / 12

Gotchas1 of 4

The trap
Gotcha 1: Filling dp row by row from i = 0
Mistake
```
for i in range(n):
    for j in range(i + 2, n):
```
Fix
```
for length in range(2, n):
    for i in range(n - length):
        j = i + length
```
What happens: dp[i][j] reads dp[k][j] for every k > i, a row further down the table. A loop from i = 0 reads those cells while they are still 0. So the total is too small. Fill by length, short ranges first, or run i from n - 1 down to 0.
Example: nums = [3, 1, 5, 8]
Mistake: returns 63Fix: returns 167
Gotcha 2: Choosing k as the first balloon to burst
Mistake
```
coins = dp[i][k] + vals[k - 1] * vals[k] * vals[k + 1] + dp[k][j]
```
Fix
```
coins = dp[i][k] + vals[i] * vals[k] * vals[j] + dp[k][j]
```
What happens: vals[k - 1] and vals[k + 1] are the neighbours of k in the original row. Those balloons may burst before k, so the product is not what k earns. When k bursts last in (i, j), its neighbours are exactly vals[i] and vals[j].
Example: nums = [3, 1, 5, 8]
Mistake: returns 98Fix: returns 167
Gotcha 3: Padding vals with 0 instead of 1
Mistake
```
vals = [0] + nums + [0]
```
Fix
```
vals = [1] + nums + [1]
```
What happens: A balloon at the edge has a missing neighbour, and the problem counts it as worth 1. The two padded balloons stand for those missing neighbours. With 0, every burst next to an edge earns 0 coins.
Example: nums = [3, 1, 5, 8]
Mistake: returns 135Fix: returns 167
Gotcha 4: Leaving cuts unsorted before building marks
Mistake
```
marks = [0] + cuts + [n]
```
Fix
```
marks = [0] + sorted(cuts) + [n]
```
What happens: In Minimum Cost to Cut a Stick (LC 1547), the item to choose is the first cut made in a piece. That cut costs the whole piece, marks[j] - marks[i]. The ranges between marks are pieces only when marks is sorted. Unsorted cuts give wrong piece lengths.
Example: Minimum Cost to Cut a Stick (LC 1547): n = 9, cuts = [5, 6, 1, 4, 2]
Mistake: returns 2Fix: returns 22

Not this one if…

Two strings are matched prefix by prefix, as in Edit Distance (LC 72): each cell comes from the cell above, to the left or diagonal, and no item inside a range has to be chosen as the split. See Two-Sequence DP
A range is judged only by its own two ends, as in Longest Palindromic Substring (LC 5): nothing inside it is removed or chosen, so there is no split point to try. See Longest Palindromic Substring
The balloons are ranges on a line and one arrow bursts every range it crosses, as in Minimum Number of Arrows to Burst Balloons (LC 452): no cost depends on what was removed before, so the order of removal never matters. See Interval Scheduling

Deep Dive

What this card adds to Interval DP

dp[i][j] is the most coins from bursting every balloon strictly between positions i and j. The balloons at i and j are not burst. They are two fixed end balloons for the whole range.

In vals = [1] + nums + [1], the two extra balloons worth 1 stand for the missing neighbours at the two ends. Then the whole problem is the single range dp[0][n - 1].

Why the last balloon splits the range

Example: in the range (0, 5) of [1, 3, 1, 5, 8, 1], k = 4 gives 159 + 1 * 8 * 1 + 0 = 167, and k = 1 gives only 162. The maximum over all k is 167.

Why the fill order is by length

dp[i][j] reads dp[i][k] and dp[k][j]. Both are ranges that are shorter than j - i. So every shorter range must be final before the longer one is computed.

The loop for length in range(2, n) fills ranges of length 2 first, then 3, and so on. The smallest range with a balloon inside has length 2, and its value is vals[i] * vals[i + 1] * vals[i + 2].

A loop that goes row by row from i = 0 reads dp[k][j] for k > i, a row that has not been filled yet. It reads 0, and the total is too small. For [3, 1, 5, 8] it returns 63 instead of 167.

The cost: ranges times split points

The card's complexity line is O(N^3) time and O(N^2) space. There are about n^2 / 2 ranges (i, j), and each tries up to n values of k.

For 100 balloons, vals has 102 entries. The loops run 171,700 times through the line that computes coins. The table dp has 102 * 102 = 10,404 cells.

60-Second Pitch

Common Questions

Why do we choose the last balloon and not the first?: The last balloon is still standing while everything else in the range bursts. So its neighbours are known (the walls), and it separates the range into two independent sides. The first balloon makes its two neighbours touch, and the sides depend on each other.
What is the time and space complexity, and why?: O(N^3) time and O(N^2) space. There are about N^2 / 2 ranges (i, j), and each range tries up to N values of k. The table dp has (N + 2)^2 cells.
Can you fill the table in another order?: Yes. Run i from n - 1 down to 0, and j from i + 2 up to n - 1. Then dp[k][j] for k > i is already final. Any order works if the two smaller ranges (i, k) and (k, j) are computed before (i, j).
How does Minimum Cost to Cut a Stick (LC 1547) fit the same template?: Use marks = [0] + sorted(cuts) + [n]. For a piece (i, j), try each mark k between them as the first cut. That cut costs marks[j] - marks[i], and the two new pieces are solved independently. Take the minimum. For n = 7 and cuts = [1, 3, 4, 5] the answer is 16.
Can this be solved with memoization?: Yes. Write solve(i, j) with a cache keyed by (i, j), and call it for (0, n - 1). It computes the same recurrence and visits only reachable ranges. The depth is at most N, and the time is still O(N^3).

SWE Reasoning

Spot it

Items in a row are removed, cut or merged one at a time, and you want the best total over all orders.
The cost of a step depends on the neighbours or on the piece at that moment, not on the item alone.
The number of orders is N!, but the problem has a natural sub-problem: a continuous range of the row.
If you fix the item that is handled last in a range, the rest splits into a left part and a right part that do not touch.
N is small, often 100 to 500 items. This allows O(N^3).

The invariant, step by step

Pad the row: vals = [1] + nums + [1]. Set n = len(vals). Create dp with n rows and n columns, all 0.
The loop sets length to 2, then 3, up to n - 1. Every range of the previous lengths is already final.
For a range (i, j), the code tries each k between them as the balloon that bursts last.
When k bursts last, everything else in the range is gone. Its neighbours are vals[i] and vals[j], so it earns vals[i] * vals[k] * vals[j].
The two sides (i, k) and (k, j) never touch, because k stands until the end. Their totals dp[i][k] and dp[k][j] are final and are added.
dp[i][j] keeps the maximum over all k. At the end, dp[0][n - 1] is the best result for the whole row.

Traps

Wrong fill order. Filling row by row from i = 0 reads cells that are still 0. For [3, 1, 5, 8] it returns 63 instead of 167.
Picking the first balloon. Using vals[k - 1] * vals[k] * vals[k + 1] assumes the original neighbours are still there. For [3, 1, 5, 8] it returns 98 instead of 167.
Padding with 0. The missing neighbour counts as 1. With 0, every burst next to an edge earns 0, and the result is 135 for [3, 1, 5, 8].
Unsorted cuts. In Minimum Cost to Cut a Stick (LC 1547), ranges between marks are pieces only if marks is sorted. For n = 9 and cuts = [5, 6, 1, 4, 2], unsorted marks return 2 instead of 22.
Range ends inside the range. If k can equal i or j, the balloon is a wall and is not burst. Use range(i + 1, j).