We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Cost Tree From Leaf Values

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem can be approached using dynamic programming to minimize the cost of non-leaf nodes.
  • Each non-leaf node's value is determined by the product of the maximum values of its left and right subtrees.
  • A monotonic stack can be useful to efficiently manage the leaf values and their combinations.
  • The minimum cost can be found by evaluating all possible splits of the array into left and right subtrees.

Space and Time Complexity

Time Complexity: O(n^2), where n is the length of the input array.
Space Complexity: O(n), for the DP table used to store intermediate results.

Solution

To solve the problem, we will use a dynamic programming approach. We will maintain a DP table where dp[i][j] represents the minimum cost of constructing a tree using the subarray arr[i:j+1]. The solution involves calculating the maximum leaf value for each segment and determining the optimal splits.

  1. Iterate over all possible lengths of the subarray.
  2. For each subarray, calculate the maximum leaf value.
  3. For each possible split point within the subarray, compute the cost and update the DP table.
  4. The final answer will be stored in dp[0][n-1], where n is the length of the array.

Code Solutions

def mctFromLeafValues(arr):
    n = len(arr)
    dp = [[0] * n for _ in range(n)]
    max_leaf = [[0] * n for _ in range(n)]

    for i in range(n):
        max_leaf[i][i] = arr[i]
        
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            max_leaf[i][j] = max(max_leaf[i][j - 1], arr[j])
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + max_leaf[i][k] * max_leaf[k + 1][j]
                dp[i][j] = min(dp[i][j], cost)

    return dp[0][n - 1]
← Back to All Questions