Minimum Cost Tree From Leaf Values

Med

#1066Time: O(n^3) - There are three nested loops. The outer two loops iterate over all possible subarrays `(i, j)`, which is O(n^2). The inner loop iterates over all possible split points `k`, which takes O(n) time. This results in a total time complexity of O(n^3).Space: O(n^2) - We use two 2D arrays, `dp` and `maxVal`, both of size n x n.2 companies

Patterns

Dynamic Programming Greedy

Data structures

Array Stack Monotonic Stack

Companies

PhonePe MathWorks

Prompt

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.

Example 2:

Input: arr = [4,11]
Output: 44

Constraints:

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 2³¹).

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses dynamic programming, a standard technique for problems with optimal substructure and overlapping subproblems. We define a function dp(i, j) that computes the minimum cost to build a tree for the subarray arr[i...j]. The final answer is dp(0, n-1).

Algorithm

Let n be the length of arr.
Create a 2D array dp[n][n] to store the minimum cost for building a tree from the subarray arr[i...j].
Create a 2D array maxVal[n][n] to store the maximum leaf value in arr[i...j]. Precompute this for efficiency.
Iterate over the length of the subarray, len, from 2 to n.
For each len, iterate over the starting index i from 0 to n-len.
The ending index j will be i + len - 1.
Initialize dp[i][j] to Integer.MAX_VALUE.
Iterate through all possible split points k from i to j-1.
Calculate the cost for the split at k: cost = dp[i][k] + dp[k+1][j] + maxVal[i][k] * maxVal[k+1][j].
Update dp[i][j] = min(dp[i][j], cost).
The final answer is dp[0][n-1].

Walkthrough

The core idea is to try every possible split point k for a given subarray arr[i...j]. A split at k divides the subarray into two parts: arr[i...k] and arr[k+1...j]. These form the left and right subtrees of a new root node. The value of this new non-leaf node is the product of the largest leaf in its left subtree (max(arr[i...k])) and the largest leaf in its right subtree (max(arr[k+1...j])). The total cost for this particular split is the sum of the costs of the subproblems (dp(i, k) and dp(k+1, j)) plus the cost of the new root. We take the minimum cost over all possible split points k.

The recurrence relation is: dp(i, j) = min_{i <= k < j} (dp(i, k) + dp(k+1, j) + max(arr[i...k]) * max(arr[k+1...j]))

The base case is dp(i, i) = 0, as a single leaf node is a tree with no non-leaf nodes and thus zero cost. We can implement this using a bottom-up approach, iterating through subarray lengths from 2 to n. To avoid recomputing maximums in subarrays repeatedly, we can precompute them in an auxiliary 2D array.

1class Solution {2    public int mctFromLeafValues(int[] arr) {3        int n = arr.length;4        int[][] dp = new int[n][n];5        int[][] maxVal = new int[n][n];6 7        for (int i = 0; i < n; i++) {8            maxVal[i][i] = arr[i];9            for (int j = i + 1; j < n; j++) {10                maxVal[i][j] = Math.max(maxVal[i][j - 1], arr[j]);11            }12        }13 14        for (int len = 2; len <= n; len++) {15            for (int i = 0; i <= n - len; i++) {16                int j = i + len - 1;17                dp[i][j] = Integer.MAX_VALUE;18                for (int k = i; k < j; k++) {19                    int cost = dp[i][k] + dp[k + 1][j] + maxVal[i][k] * maxVal[k + 1][j];20                    dp[i][j] = Math.min(dp[i][j], cost);21                }22            }23        }24        return dp[0][n - 1];25    }26}

Complexity

Time

O(n^3) - There are three nested loops. The outer two loops iterate over all possible subarrays `(i, j)`, which is O(n^2). The inner loop iterates over all possible split points `k`, which takes O(n) time. This results in a total time complexity of O(n^3).

Space

O(n^2) - We use two 2D arrays, `dp` and `maxVal`, both of size n x n.

Trade-offs

Pros

Conceptually straightforward and follows a standard DP pattern similar to Matrix Chain Multiplication.
Guaranteed to find the optimal solution by exploring all possibilities systematically.

Cons

The cubic time complexity makes it slow for larger constraints, although it passes for N <= 40.
Requires quadratic space, which can be memory-intensive.

This approach is based on a greedy insight. The problem can be rephrased as: repeatedly find a pair of adjacent numbers in a list, calculate their product, add it to the total cost, and replace the pair with their maximum. The greedy strategy is to always find the smallest number in the current list and combine it with its smaller neighbor to minimize the cost contribution at each step.

Algorithm

Convert the input array arr into a List for easier element removal.
Initialize a variable totalCost to 0.
Loop n-1 times, as we need to perform n-1 combinations to form the final tree: a. Find the index minIdx of the minimum value in the current list. b. Determine the cost. If minIdx is at a boundary, the cost is the product of the minimum value and its single neighbor. Otherwise, it's the product of the minimum value and the smaller of its two neighbors. c. Add this cost to totalCost. d. Remove the element at minIdx from the list.
Return totalCost.

Walkthrough

The key observation is that each number arr[i] (except for the overall maximum in the array) must eventually be the smaller element in a product pair, effectively being 'removed' from the list of potential maximums. To minimize its contribution arr[i] * partner, we should choose the smallest possible partner. The best partners are its immediate neighbors in the current sequence.

The greedy strategy is to find the smallest element in the current list of numbers, say x. x is then paired with the smaller of its two adjacent neighbors. This operation corresponds to forming a new non-leaf node. We simulate this process by starting with a list of all numbers from arr. In each step, we find the minimum element, calculate the cost, add this cost to our total, and remove the minimum element from the list. This is repeated n-1 times until only one element remains.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int mctFromLeafValues(int[] arr) {6        List<Integer> list = new ArrayList<>();7        for (int num : arr) {8            list.add(num);9        }10        int res = 0;11        while (list.size() > 1) {12            int minVal = Integer.MAX_VALUE;13            int minIdx = -1;14            for (int i = 0; i < list.size(); i++) {15                if (list.get(i) < minVal) {16                    minVal = list.get(i);17                    minIdx = i;18                }19            }20            21            int leftNeighbor = (minIdx > 0) ? list.get(minIdx - 1) : Integer.MAX_VALUE;22            int rightNeighbor = (minIdx < list.size() - 1) ? list.get(minIdx + 1) : Integer.MAX_VALUE;23            24            res += minVal * Math.min(leftNeighbor, rightNeighbor);25            list.remove(minIdx);26        }27        return res;28    }29}

Complexity

Time

O(n^2) - The process is repeated `n-1` times. In each iteration, finding the minimum element takes O(n) time, and removing an element from an `ArrayList` can also take O(n) time in the worst case.

Space

O(n) - We use a list to store the numbers, which takes space proportional to the input size.

Trade-offs

Pros

More efficient than the O(n^3) DP approach.
The greedy logic is relatively easy to understand.

Cons

The simulation using a standard list (like Java's ArrayList) is inefficient. Finding the minimum and removing an element both take O(n) time, leading to a quadratic overall complexity.

This is the most optimal approach, which implements the greedy strategy in linear time using a monotonic stack. The core idea is that when an element arr[i] is chosen to be a smaller part of a product, it's paired with the nearest greater element on its left or right. A monotonic stack is the perfect data structure to find these elements efficiently.

Algorithm

Initialize totalCost = 0 and an empty stack.
To simplify boundary conditions, push a sentinel value like Integer.MAX_VALUE onto the stack first.
Iterate through each number num in the input array arr.
While the element at the top of the stack is less than or equal to the current number num: a. Pop the top element, let's call it mid. b. mid is now paired up. Its right partner is num. Its left partner is the new top of the stack. c. Add the cost mid * min(stack.peek(), num) to totalCost.
Push the current number num onto the stack. This maintains the monotonically decreasing property of the stack.
After iterating through the entire array, the stack will contain a decreasing sequence of numbers (plus the sentinel). These are the largest leaf values of subtrees that haven't been merged yet.
While the stack has more than two elements (the last element and the sentinel), pop the top element and multiply it by the new top, adding the result to totalCost.
Return totalCost.

Walkthrough

We maintain a monotonically decreasing stack. The stack stores leaf values that are candidates for being the larger value in a future product. We iterate through the input array arr. For each number x, we compare it with the top of the stack.

If x is greater than the stack's top element, it means x is the first greater element to the right for the element at the top of the stack. We pop elements from the stack as long as they are smaller than or equal to x. For each popped element mid, we calculate its contribution to the cost. The partners for mid are x (its nearest greater element on the right) and the new stack top (its nearest greater element on the left, due to the stack's decreasing nature). We multiply mid by the smaller of these two partners and add it to the total cost.

After this, we push x onto the stack to maintain the decreasing order. After iterating through the entire array, any remaining elements in the stack form a decreasing sequence. We process them by repeatedly pairing adjacent elements until only one is left.

1import java.util.Stack;2 3class Solution {4    public int mctFromLeafValues(int[] arr) {5        int res = 0;6        Stack<Integer> stack = new Stack<>();7        stack.push(Integer.MAX_VALUE); // Sentinel value8 9        for (int num : arr) {10            while (stack.peek() <= num) {11                int mid = stack.pop();12                res += mid * Math.min(stack.peek(), num);13            }14            stack.push(num);15        }16 17        while (stack.size() > 2) {18            res += stack.pop() * stack.peek();19        }20        21        return res;22    }23}

Complexity

Time

O(n) - Each element from the input array `arr` is pushed onto the stack exactly once and popped from the stack at most once. Therefore, the overall time complexity is linear.

Space

O(n) - In the worst-case scenario (e.g., a decreasingly sorted array), the stack can hold all `n` elements.

Trade-offs

Pros

Optimal O(n) time complexity.
Efficient O(n) space complexity.
Provides an elegant and concise solution to the problem.

Cons

The logic, especially the connection between the monotonic stack and the greedy choice, can be less intuitive to derive compared to the DP approach.

Solutions

Solution

1class Solution { private Integer [][] f ; private int [][] g ; public int mctFromLeafValues ( int [] arr ) { int n = arr . length ; f = new Integer [ n ][ n ]; g = new int [ n ][ n ]; for ( int i = n - 1 ; i >= 0 ; -- i ) { g [ i ][ i ] = arr [ i ]; for ( int j = i + 1 ; j < n ; ++ j ) { g [ i ][ j ] = Math . max ( g [ i ][ j - 1 ], arr [ j ]); } } return dfs ( 0 , n - 1 ); } private int dfs ( int i , int j ) { if ( i == j ) { return 0 ; } if ( f [ i ][ j ] != null ) { return f [ i ][ j ]; } int ans = 1 << 30 ; for ( int k = i ; k < j ; k ++) { ans = Math . min ( ans , dfs ( i , k ) + dfs ( k + 1 , j ) + g [ i ][ k ] * g [ k + 1 ][ j ]); } return f [ i ][ j ] = ans ; } }

1class Solution { public: int mctFromLeafValues ( vector < int >& arr ) { int n = arr . size (); int f [ n ][ n ]; int g [ n ][ n ]; memset ( f , 0 , sizeof ( f )); for ( int i = n - 1 ; ~ i ; -- i ) { g [ i ][ i ] = arr [ i ]; for ( int j = i + 1 ; j < n ; ++ j ) { g [ i ][ j ] = max ( g [ i ][ j - 1 ], arr [ j ]); } } function < int ( int , int ) > dfs = [ & ]( int i , int j ) -> int { if ( i == j ) { return 0 ; } if ( f [ i ][ j ] > 0 ) { return f [ i ][ j ]; } int ans = 1 << 30 ; for ( int k = i ; k < j ; ++ k ) { ans = min ( ans , dfs ( i , k ) + dfs ( k + 1 , j ) + g [ i ][ k ] * g [ k + 1 ][ j ]); } return f [ i ][ j ] = ans ; }; return dfs ( 0 , n - 1 ); } };

1class Solution : def mctFromLeafValues ( self , arr : List [ int ]) -> int : @ cache def dfs ( i : int , j : int ) -> Tuple : if i == j : return 0 , arr [ i ] s , mx = inf , - 1 for k in range ( i , j ): s1 , mx1 = dfs ( i , k ) s2 , mx2 = dfs ( k + 1 , j ) t = s1 + s2 + mx1 * mx2 if s > t : s = t mx = max ( mx1 , mx2 ) return s , mx return dfs ( 0 , len ( arr ) - 1 )[ 0 ]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution { private Integer [][] f ; private int [][] g ; public int mctFromLeafValues ( int [] arr ) { int n = arr . length ; f = new Integer [ n ][ n ]; g = new int [ n ][ n ]; for ( int i = n - 1 ; i >= 0 ; -- i ) { g [ i ][ i ] = arr [ i ]; for ( int j = i + 1 ; j < n ; ++ j ) { g [ i ][ j ] = Math . max ( g [ i ][ j - 1 ], arr [ j ]); } } return dfs ( 0 , n - 1 ); } private int dfs ( int i , int j ) { if ( i == j ) { return 0 ; } if ( f [ i ][ j ] != null ) { return f [ i ][ j ]; } int ans = 1 << 30 ; for ( int k = i ; k < j ; k ++) { ans = Math . min ( ans , dfs ( i , k ) + dfs ( k + 1 , j ) + g [ i ][ k ] * g [ k + 1 ][ j ]); } return f [ i ][ j ] = ans ; } }

1class Solution { public: int mctFromLeafValues ( vector < int >& arr ) { int n = arr . size (); int f [ n ][ n ]; int g [ n ][ n ]; memset ( f , 0 , sizeof ( f )); for ( int i = n - 1 ; ~ i ; -- i ) { g [ i ][ i ] = arr [ i ]; for ( int j = i + 1 ; j < n ; ++ j ) { g [ i ][ j ] = max ( g [ i ][ j - 1 ], arr [ j ]); } } function < int ( int , int ) > dfs = [ & ]( int i , int j ) -> int { if ( i == j ) { return 0 ; } if ( f [ i ][ j ] > 0 ) { return f [ i ][ j ]; } int ans = 1 << 30 ; for ( int k = i ; k < j ; ++ k ) { ans = min ( ans , dfs ( i , k ) + dfs ( k + 1 , j ) + g [ i ][ k ] * g [ k + 1 ][ j ]); } return f [ i ][ j ] = ans ; }; return dfs ( 0 , n - 1 ); } };

1class Solution : def mctFromLeafValues ( self , arr : List [ int ]) -> int : @ cache def dfs ( i : int , j : int ) -> Tuple : if i == j : return 0 , arr [ i ] s , mx = inf , - 1 for k in range ( i , j ): s1 , mx1 = dfs ( i , k ) s2 , mx2 = dfs ( k + 1 , j ) t = s1 + s2 + mx1 * mx2 if s > t : s = t mx = max ( mx1 , mx2 ) return s , mx return dfs ( 0 , len ( arr ) - 1 )[ 0 ]

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.