1130. Minimum Cost Tree From Leaf Values LeetCode Solution
In this guide, you will get 1130. Minimum Cost Tree From Leaf Values LeetCode Solution with the best time and space complexity. The solution to Minimum Cost Tree From Leaf Values problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Cost Tree From Leaf Values
Given an array arr of positive integers, consider all binary trees such that:
Each node has either 0 or 2 children;
The values of arr correspond to the values of each leaf in an in-order traversal of the tree.
The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree, respectively.
Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf node. It is guaranteed this sum fits into a 32-bit integer.
A node is a leaf if and only if it has zero children.
Example 1:
Input: arr = [6,2,4]
Output: 32
Explanation: There are two possible trees shown.
The first has a non-leaf node sum 36, and the second has non-leaf node sum 32.
2 <= arr.length <= 40
1 <= arr[i] <= 15
It is guaranteed that the answer fits into a 32-bit signed integer (i.e., it is less than 231).
Complexity Analysis
Time Complexity: O(n^3)
Space Complexity: O(n^2)
1130. Minimum Cost Tree From Leaf Values LeetCode Solution in C++
class Solution {
public:
int mctFromLeafValues(vector<int>& arr) {
const int n = arr.size();
// dp[i][j] := the minimum cost of arr[i..j]
vector<vector<int>> dp(n, vector<int>(n));
// maxVal[i][j] := the maximum value of arr[i..j]
vector<vector<int>> maxVal(n, vector<int>(n));
for (int i = 0; i < n; ++i)
maxVal[i][i] = arr[i];
for (int d = 1; d < n; ++d)
for (int i = 0; i + d < n; ++i) {
const int j = i + d;
maxVal[i][j] = max(maxVal[i][j - 1], maxVal[i + 1][j]);
}
for (int d = 1; d < n; ++d)
for (int i = 0; i + d < n; ++i) {
const int j = i + d;
dp[i][j] = INT_MAX;
for (int k = i; k < j; ++k)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] +
maxVal[i][k] * maxVal[k + 1][j]);
}
return dp[0].back();
}
}; /* code provided by PROGIEZ */
1130. Minimum Cost Tree From Leaf Values LeetCode Solution in Java
class Solution {
public int mctFromLeafValues(int[] arr) {
final int n = arr.length;
// dp[i][j] := the minimum cost of arr[i..j]
int[][] dp = new int[n][n];
// maxVal[i][j] := the maximum value of arr[i..j]
int[][] maxVal = new int[n][n];
for (int i = 0; i < n; ++i)
maxVal[i][i] = arr[i];
for (int d = 1; d < n; ++d)
for (int i = 0; i + d < n; ++i) {
final int j = i + d;
maxVal[i][j] = Math.max(maxVal[i][j - 1], maxVal[i + 1][j]);
}
for (int d = 1; d < n; ++d)
for (int i = 0; i + d < n; ++i) {
final int j = i + d;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; ++k)
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + maxVal[i][k] * maxVal[k + 1][j]);
}
return dp[0][n - 1];
}
} // code provided by PROGIEZ
1130. Minimum Cost Tree From Leaf Values LeetCode Solution in Python
class Solution:
def mctFromLeafValues(self, arr: list[int]) -> int:
n = len(arr)
# dp[i][j] := the minimum cost of arr[i..j]
dp = [[0] * n for _ in range(n)]
# maxVal[i][j] := the maximum value of arr[i..j]
maxVal = [[0] * n for _ in range(n)]
for i in range(n):
maxVal[i][i] = arr[i]
for d in range(1, n):
for i in range(n - d):
j = i + d
maxVal[i][j] = max(maxVal[i][j - 1], maxVal[i + 1][j])
for d in range(1, n):
for i in range(n - d):
j = i + d
dp[i][j] = math.inf
for k in range(i, j):
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] +
maxVal[i][k] * maxVal[k + 1][j])
return dp[0][-1] # code by PROGIEZ
