Burst Balloons – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
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.
Example 1:
Input: nums = [3,1,5,8] Output: 167 Explanation: nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> [] coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
Example 2:
Input: nums = [1,5] Output: 10
Constraints:
n == nums.length
1 <= n <= 300
0 <= nums[i] <= 100
C++ Burst Balloons LeetCode Solution
class Solution {
public:
int n;
int t[501][501]; // For memoization
int solve(vector<int> &nums, int i, int j){
// BASE CASES
if(i > j)
return 0;
if(i == j){ // Only one element exists
int temp = nums[i];
if(i - 1 >= 0)
temp *= nums[i - 1];
if(i + 1 < n)
temp *= nums[i + 1];
return temp;
}
if(t[i][j] != -1) // Check if the solution is already stored for this subproblem
return t[i][j];
int ans = 0;
// For all elements in the range i to j, we choose all of them one by one
// to make them the last balloon to be burst.
for(int k = i; k <= j; k++){
// Burst the kth balloon after bursting (i, k - 1) and (k + 1, j) balloons
int temp = nums[k];
if(j + 1 < n) // As balloon j + 1 will become adjacent to k after bursting k + 1 to j balloons
temp *= nums[j + 1];
if(i - 1 >= 0) // As balloon i- 1 will become adjacent to k after bursting i to k -1 balloons
temp *= nums[i - 1];
// Recursively solve the left and right subproblems and add their contribution
temp += (solve(nums, i, k - 1) + solve(nums, k + 1, j));
// If this choice of k yields a better answer
ans = max(ans, temp);
}
return t[i][j] = ans;
}
int maxCoins(vector<int>& nums) {
memset(t, -1, sizeof(t));
// Insert two dummy balloons of value 1 to handle the balloons on the corner.
vector<int> arr = {1};
for(int x: nums)
arr.push_back(x);
arr.push_back(1);
n = arr.size();
//Start from i = 1 and j = arr.size() - 2 since first and last balloons are dummy.
return solve(arr, 1, arr.size() - 2);
}
};
Java Burst Balloons LeetCode Solution
public int maxCoins(int[] nums) {
int[][] dp = new int[nums.length][nums.length];
return maxCoins(nums, 0, nums.length - 1, dp);
}
public int maxCoins(int[] nums, int start, int end, int[][] dp) {
if (start > end) {
return 0;
}
if (dp[start][end] != 0) {
return dp[start][end];
}
int max = nums[start];
for (int i = start; i <= end; i++) {
int val = maxCoins(nums, start, i - 1, dp) +
get(nums, i) * get(nums, start - 1) * get(nums, end + 1) +
maxCoins(nums, i + 1, end, dp);
max = Math.max(max, val);
}
dp[start][end] = max;
return max;
}
public int get(int[] nums, int i) {
if (i == -1 || i == nums.length) {
return 1;
}
return nums[i];
}
Python 3 Burst Balloons LeetCode Solution
class Solution:
def maxCoins(self, A):
A, n = [1] + A + [1], len(A) + 2
dp = [[0] * n for _ in range(n)]
for i in range(n - 2, -1, -1):
for j in range(i + 2, n):
dp[i][j] = max(A[i]*A[k]*A[j] + dp[i][k] + dp[k][j] for k in range(i + 1, j))
return dp[0][n-1]
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
Leave a comment below