Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Burst Balloons
Bookmark
Input
Example 1
Example 2
Three Balloons
Sequential
All Same
Custom
nums
=
[3, 1, 5, 8]
balloons =
4
3
1
1
2
5
3
8
4
r2
r3
r4
r5
l0
l1
l2
l3
each burst pays left x self x right of the balloons still standing
balloons =
4
3
1
1
2
5
3
8
4
r2
r3
r4
r5
l0
l1
l2
l3
each burst pays left x self x right of the balloons still standing
balloons =
4
1
0
3
1
1
2
5
3
8
4
1
5
r2
r3
r4
r5
l0
l1
l2
l3
3
3
gap (0, 2) settled: burst
3
last
balloons =
4
1
0
3
1
1
2
5
3
8
4
1
5
r2
r3
r4
r5
l0
l1
l2
l3
3
3
15
1
40
5
dp[2][4]
=
40
new best for this gap
balloons =
4
1
0
3
1
1
2
5
3
8
4
1
5
r2
r3
r4
r5
l0
l1
l2
l3
3
3
15
1
40
5
40
8
gap (0, 3)
which balloon bursts LAST between them?
balloons =
4
1
0
3
1
1
2
5
3
8
4
1
5
r2
r3
r4
r5
l0
l1
l2
l3
3
3
30
3
15
1
64
1
40
5
40
8
dp[1][4]
=
64
new best for this gap
balloons =
4
1
0
3
1
1
2
5
3
8
4
1
5
r2
r3
r4
r5
l0
l1
l2
l3
3
3
30
3
15
1
135
5
40
5
45
5
40
8
dp[2][5]
=
45
new best for this gap
balloons =
4
1
0
3
1
1
2
5
3
8
4
1
5
r2
r3
r4
r5
l0
l1
l2
l3
3
3
30
3
159
3
15
1
135
5
40
5
48
8
40
8
dp[0][4]
=
159
new best for this gap
balloons =
4
1
0
3
1
1
2
5
3
8
4
1
5
r2
r3
r4
r5
l0
l1
l2
l3
3
3
30
3
159
3
15
1
135
5
51
1
40
5
48
8
40
8
burst
5
last:
15
+
3x5x1
+
40
=
70
balloons =
4
1
0
3
1
1
2
5
3
8
4
1
5
r2
r3
r4
r5
l0
l1
l2
l3
3
3
30
3
159
3
15
1
135
5
159
8
40
5
48
8
40
8
burst
3
last:
0
+
1x3x1
+
159
=
162
balloons =
4
1
0
3
1
3
1
2
1
5
3
2
8
4
4
1
5
r2
r3
r4
r5
l0
l1
l2
l3
3
3
30
3
159
3
167
8
15
1
135
5
159
8
40
5
48
8
40
8
max coins =
167
= 15 + 120 + 24 + 8
algo
master
.
io
Step:
Burst every balloon. Each burst pays left x self x right of the balloons still standing
0 / 62
Input
Example 1
Example 2
Three Balloons
Sequential
All Same
Custom
nums
=
[3, 1, 5, 8]
0 / 62
algo
master
.
io
Step:
Burst every balloon. Each burst pays left x self x right of the balloons still standing
