1130. Minimum Cost Tree From Leaf Values
Problem Description
The problem given asks us to construct binary trees based on certain conditions and calculate the sum of the values of each non-leaf node. The special conditions provided for the binary trees are:
- Each node in the tree either has no children (making it a leaf) or has exactly two children (non-leaf nodes).
- The sequence of values found at the leaf nodes must match the sequence given by array
arr
in an in-order traversal. - For each non-leaf node, its value is determined as the product of the largest leaf value from its left subtree and the largest leaf value from its right subtree.
The goal is to find the binary tree which results in the smallest sum of the values of all the non-leaf nodes combined, and return this minimum possible sum. It's guaranteed that the result will fit within a 32-bit integer.
Intuition
The intuition behind the solution comes from the fact that constructing a tree with a lower sum of non-leaf nodes heavily depends on how we group the elements to form subtrees, and consequently, the products at non-leaf nodes. As such, we want to ensure that smaller numbers participate in more products while larger numbers should be used less often to keep the sum as small as possible.
A dynamic programming approach allows us to solve this efficiently. We can define a two-dimensional array f
where f[i][j]
represents the minimum sum of the values of non-leaf nodes for the subarray arr[i]
to arr[j]
. A companion array g
stores the maximum leaf values we can have between indices i
and j
. This is done because we know that each non-leaf node's value equals the product of the largest leaf value in each of its left and right subtrees. So, g[i][j]
helps us quickly determine those products as we build our solution.
By starting with subarrays of length 1 and extending to the full length of arr
, we can systematically find the minimum sum for any given segment of arr
. We do so by iterating through every possible division within a subarray, creating potential left and right subtrees, computing their respective non-leaf node value, and maintaining the minimum result for each segment.
The final answer will be the value of f[0][n - 1]
which represents the minimum sum for the entire array arr
converted into a binary tree following the described criteria.
Learn more about Stack, Greedy, Dynamic Programming and Monotonic Stack patterns.
Solution Approach
The implementation of the solution utilizes dynamic programming, which is a method to solve complex problems by breaking them down into simpler subproblems and solving each of these subproblems just once, storing their solutions ā usually in an array.
Letās dive into the step-by-step explanation of the code:
Step 1: Initialization
Two two-dimensional arrays, f
and g
, are initialized with dimensions n x n
, where n
is the length of the given array arr
. Here, n
represents the range of subarrays we will consider (from arr[i]
to arr[j]
inclusively):
f[i][j]
will store the minimum sum of the non-leaf nodes for the subarrayarr[i]
toarr[j]
.g[i][j]
will store the maximum leaf value in the subarrayarr[i]
toarr[j]
.
n = len(arr)
f = [[0] * n for _ in range(n)]
g = [[0] * n for _ in range(n)]
Step 2: Populate the g
array
The g
array is filled with the maximum leaf values. This step is crucial because it allows for quick access to the maximum leaf values later when calculating the non-leaf node values. To fill g
, we iterate over all possible subarrays and populate g[i][j]
with the maximum value between arr[j]
and the current maximum g[i][j - 1]
:
for i in range(n - 1, -1, -1):
g[i][i] = arr[i]
for j in range(i + 1, n):
g[i][j] = max(g[i][j - 1], arr[j])
Step 3: Calculate the minimum sum of non-leaf nodes
The main logic for solving the problem resides here, where f[i][j]
is computed for different subarrays. The idea is to iterate through all possible splits k
of the subarray arr[i]
to arr[j]
into two parts, arr[i]
to arr[k]
and arr[k + 1]
to arr[j]
. For each split, we calculate:
- The sum of non-leaf nodes for both parts (
f[i][k]
andf[k + 1][j]
), which have already been calculated thanks to the dynamic programming approach. - The product of the maximum leaf values for the left and right subtrees (
g[i][k] * g[k + 1][j]
), which gives the value of the root for this particular binary tree formed by this split.
We keep track of the minimum sum obtained among all possible splits, and that becomes the value of f[i][j]
:
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
f[i][j] = min(
f[i][k] + f[k + 1][j] + g[i][k] * g[k + 1][j] for k in range(i, j)
)
Step 4: Return the result
Finally, f[0][n - 1]
gives us the minimum sum for the entire array arr
, and thus, is returned as the final result:
return f[0][n - 1]
This implementation effectively breaks down the complex task of finding the optimal binary tree into manageable subproblems, whose results are stored and reused ā demonstrating the efficacy of dynamic programming.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take a small example to illustrate how the solution approach works. Suppose we have the array arr
given as [3, 11, 2, 5]
. We want to construct a binary tree following the conditions mentioned and determine the minimum sum of non-leaf nodes' values.
Visualizing the Problem:
For arr
= [3, 11, 2, 5]
, the in-order traversal of the leaf nodes in the binary tree must be [3, 11, 2, 5]
.
Step 1: Fill in g
for maximum leaf values
We compute g[i][j]
for all subarrays:
- For subarrays of length 1 (i.e., single elements),
g[i][i]
=arr[i]
. - For longer subarrays, we would compute the maximum as follows:
g[0][1] = max(arr[0], arr[1]) = max(3, 11) = 11 g[1][2] = max(arr[1], arr[2]) = max(11, 2) = 11 g[2][3] = max(arr[2], arr[3]) = max(2, 5) = 5
- And so on, for all subarray combinations.
Step 2: Populate g
using dynamic programming
Here's the filled g
matrix for our example array:
g = [ [3, 11, 11, 11], [0, 11, 11, 11], [0, 0, 2, 5], [0, 0, 0, 5] ]
Step 3: Calculate f
for minimum sums of non-leaf nodes
Now we need to compute f[i][j]
. Being a dynamic programming solution, we start with the smallest subarrays and move to larger ones.
- For subarrays of length 1 (single elements),
f[i][i]
= 0, as single elements are leaf nodes and don't contribute to the sum of non-leaf nodes. - Then we consider all subarrays of length 2 and above. For our example, let's compute
f[0][2]
which represents the subarray[3, 11, 2]
.
We would need to consider splitting this subarray into [3]
and [11, 2]
or [3, 11]
and [2]
. We'll compute the sum of non-leaf nodes for both scenarios:
For split [3]
and [11, 2]
, the sum would be f[0][0] + f[1][2] + g[0][0] * g[1][2]
.
Here, f[0][0]
and f[1][2]
are 0 (since f
is initialized with zeros and gets updated gradually), and g[0][0] * g[1][2]
is 3 * 11
.
For split [3, 11]
and [2]
, the sum would be f[0][1] + f[2][2] + g[0][1] * g[2][2]
.
In this case f[0][1]
and f[2][2]
are again 0, and g[0][1] * g[2][2]
is 11 * 2
.
So, f[0][2] = min((0 + 0 + 3 * 11), (0 + 0 + 11 * 2)) = min(33, 22) = 22
.
- We compute
f[i][j]
for all possiblei
andj
in a similar fashion.
Step 4: Construct f
matrix and determine the result
We proceed computing f
values for increasingly larger subarrays of arr
, keeping track of the minimum sum of non-leaf nodes using dynamic programming.
After filling out the f
matrix, we'll get:
f = [ [0, 33, 22, min_sum], [0, 0, 22, min_sum], [0, 0, 0, 10], [0, 0, 0, 0] ]
The min_sum
in f[0][3]
will be the final answer, which is computed by considering all the possibilities, as we just did for f[0][2]
.
By following these steps and populating f
and g
, we find that f[0][3]
equals the minimum sum of the binary tree non-leaf nodes constructed from array arr
, following the given conditions.
In this way, the dynamic programming solution helps us reduce the complexity of the problem by avoiding redundant calculations and focusing on subproblems, storing and reusing the solutions as the algorithm progresses.
Solution Implementation
1from typing import List
2
3class Solution:
4 def mctFromLeafValues(self, arr: List[int]) -> int:
5 # n is the length of the array
6 n = len(arr)
7
8 # 'dp' will store minimum total sum needed to merge the trees
9 dp = [[0] * n for _ in range(n)]
10
11 # 'max_matrix' will keep track of the maximum leaf value from arr[i] to arr[j]
12 max_matrix = [[0] * n for _ in range(n)]
13
14 # Fill out 'max_matrix' and 'dp' diagonally
15 for start in range(n - 1, -1, -1):
16 # On the diagonal, the max value is the value itself since it's a single leaf
17 max_matrix[start][start] = arr[start]
18 for end in range(start + 1, n):
19 # For each interval from 'start' to 'end', find the max leaf in this range
20 max_matrix[start][end] = max(max_matrix[start][end - 1], arr[end])
21
22 # Set an initial high value to compare against in the first iteration
23 dp[start][end] = float('inf')
24
25 # Now calculate the minimum sum by breaking the interval into two parts
26 # and find the pair that provides minimum sum when merged
27 for k in range(start, end):
28 dp[start][end] = min(
29 dp[start][end],
30 dp[start][k] + dp[k + 1][end] + max_matrix[start][k] * max_matrix[k + 1][end]
31 )
32
33 # Return the minimum sum for the interval from 0 to n-1, which represents the whole array
34 return dp[0][n - 1]
35
36# Example usage:
37# sol = Solution()
38# result = sol.mctFromLeafValues([6, 2, 4])
39# print(result) # Output would be the minimum possible sum
40
1public class Solution {
2
3 public int mctFromLeafValues(int[] arr) {
4 int size = arr.length; // Get the size of the array
5
6 int[][] dp = new int[size][size]; // Create a DP array to store minimum cost
7 int[][] maxLeafValue = new int[size][size]; // Create an array to store max leaf value in the subarray [i...j]
8
9 // Fill the maxLeafValue array by iterating from the end to the beginning
10 // The value maxLeafValue[i][j] represents the maximum leaf value in the subarray arr[i...j]
11 for (int i = size - 1; i >= 0; --i) {
12 maxLeafValue[i][i] = arr[i]; // A single leaf's max value is itself
13 for (int j = i + 1; j < size; ++j) {
14 maxLeafValue[i][j] = Math.max(maxLeafValue[i][j - 1], arr[j]);
15 dp[i][j] = Integer.MAX_VALUE; // Initialize the DP array with max values
16
17 // Compute the minimum cost for subarray [i...j] by trying out all possible partitions
18 for (int k = i; k < j; ++k) {
19 dp[i][j] = Math.min(dp[i][j],
20 dp[i][k] + dp[k + 1][j] + maxLeafValue[i][k] * maxLeafValue[k + 1][j]);
21 }
22 }
23 }
24
25 // Return the final answer, which is the minimum cost for the whole array
26 return dp[0][size - 1];
27 }
28}
29
1#include <vector>
2#include <cstring>
3using namespace std;
4
5class Solution {
6public:
7 int mctFromLeafValues(vector<int>& arr) {
8 int size = arr.size(); // 'n' is renamed to 'size' for clarity.
9 int dp[size][size]; // 'f' is renamed to 'dp' to indicate it is used for dynamic programming.
10 int maxInRange[size][size]; // 'g' is renamed to 'maxInRange' indicating it stores the maximum values in ranges.
11
12 // Initialize the dp matrix with zeroes.
13 memset(dp, 0, sizeof(dp));
14
15 // Iterate over the array in reverse to build the maximum values in ranges.
16 for (int i = size - 1; i >= 0; --i) {
17 maxInRange[i][i] = arr[i]; // Initialize the diagonal with the same array values.
18 for (int j = i + 1; j < size; ++j) {
19 // Fill maxInRange[i][j] with the maximum value found between i and j.
20 maxInRange[i][j] = max(maxInRange[i][j - 1], arr[j]);
21
22 dp[i][j] = INT_MAX; // Initialize the cell with the maximum possible value.
23 for (int k = i; k < j; ++k) {
24 // Calculate the minimum cost for the range i to j by partitioning the range at k.
25 dp[i][j] = min(dp[i][j],
26 dp[i][k] + dp[k + 1][j] + maxInRange[i][k] * maxInRange[k + 1][j]);
27 }
28 }
29 }
30
31 // Return the minimum cost to build the tree from the root (0, size-1).
32 return dp[0][size - 1];
33 }
34};
35
1// Function to calculate the minimum cost to merge the leaf values.
2function mctFromLeafValues(arr: number[]): number {
3 // Get the length of the input array.
4 const length = arr.length;
5
6 // Initialize the dp arrays with default values.
7 const dp: number[][] = new Array(length).fill(0).map(() => new Array(length).fill(0));
8 const maxLeafValue: number[][] = new Array(length).fill(0).map(() => new Array(length).fill(0));
9
10 // Process the array in reverse.
11 for (let start = length - 1; start >= 0; --start) {
12 // Base case where the interval only contains a single element.
13 maxLeafValue[start][start] = arr[start];
14
15 // Process all possible pairs of intervals (start, end).
16 for (let end = start + 1; end < length; ++end) {
17 // Determine the maximum leaf value in the current interval.
18 maxLeafValue[start][end] = Math.max(maxLeafValue[start][end - 1], arr[end]);
19 // Initialize the minimum cost to be a large number.
20 dp[start][end] = Number.MAX_SAFE_INTEGER;
21
22 // Try to divide the current interval into two intervals ([start, mid], [mid + 1, end])
23 // and find the minimum cost for this division approach.
24 for (let mid = start; mid < end; ++mid) {
25 dp[start][end] = Math.min(dp[start][end], dp[start][mid] + dp[mid + 1][end] + maxLeafValue[start][mid] * maxLeafValue[mid + 1][end]);
26 }
27 }
28 }
29
30 // Return the minimum cost to merge the entire range of leaves.
31 return dp[0][length - 1];
32}
33
Time and Space Complexity
The given code is a dynamic programming solution designed to minimize the sum of the products of non-leaf nodes' values in a binary tree built from an array, where each leaf is a value from the array. We'll analyze both time complexity and space complexity.
Time Complexity:
We have a nested loop where i
goes from n-1
to 0
and for each i
, j
goes from i+1
to n
, and within each pair of i
and j
, there is an inner loop where k
goes from i
to j-1
. The time complexity can be evaluated as the sum of the series in the form of a cubic polynomial.
The number of times the innermost operation (the min
calculation) is executed can be roughly approximated by the cubic sum Ī£ (i=1 to n) Ī£ (j=i+1 to n) Ī£ (k=i to j-1) 1
, which simplifies to O(n^3)
where n
is the length of the array.
Thus, the time complexity of this solution is O(n^3)
.
Space Complexity:
The space complexity is determined by the two 2D arrays f
and g
which are each of size n*n
, where n
is the length of the input array arr
. There are no other data structures that scale with the input size. Hence, the space complexity is O(n^2)
due to these two 2D arrays.
Learn more about how to find time and space complexity quickly using problem constraints.
A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".
What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Want a Structured Path to Master System Design Too? Donāt Miss This!