1130. Minimum Cost Tree From Leaf Values

Approach 1: DP

• Time: $O(n^3)$
• Space: $O(n^2)$

C++JavaPython

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();
  }
};

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];
  }
}

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]

Approach 2: Intuition

• Time: $O(n^2)$
• Space: $O(n)$

C++JavaPython

class Solution {
 public:
  int mctFromLeafValues(vector<int>& arr) {
    int ans = 0;
    vector<int> stack{INT_MAX};

    for (const int a : arr) {
      while (stack.back() <= a) {
        const int mid = stack.back();
        stack.pop_back();
        // Multiply mid with next greater element in the array,
        // On the left (stack[-1]) or on the right (current number a)
        ans += min(stack.back(), a) * mid;
      }
      stack.push_back(a);
    }

    for (int i = 2; i < stack.size(); ++i)
      ans += stack[i] * stack[i - 1];

    return ans;
  }
};

class Solution {
  public int mctFromLeafValues(int[] arr) {
    int ans = 0;
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(Integer.MAX_VALUE);

    for (final int a : arr) {
      while (stack.peek() <= a) {
        final int mid = stack.pop();
        // Multiply mid with next greater element in the array,
        // On the left (stack[-1]) or on the right (current number a)
        ans += Math.min(stack.peek(), a) * mid;
      }
      stack.push(a);
    }

    while (stack.size() > 2)
      ans += stack.pop() * stack.peek();

    return ans;
  }
}

class Solution:
  def mctFromLeafValues(self, arr: list[int]) -> int:
    ans = 0
    stack = [math.inf]

    for a in arr:
      while stack and stack[-1] <= a:
        mid = stack.pop()
        # Multiply mid with next greater element in the array,
        # On the left (stack[-1]) or on the right (current number a)
        ans += min(stack[-1], a) * mid
      stack.append(a)

    return ans + sum(a * b for a, b in zip(stack[1:], stack[2:]))

Approach 3: Stack

• Time: $O(n)$
• Space: $O(n)$

Python

class Solution:
  def mctFromLeafValues(self, arr: list[int]) -> int:
    ans = 0

    while len(arr) > 1:
      i = arr.index(min(arr))
      ans += min(arr[i - 1:i] + arr[i + 1:i + 2]) * arr.pop(i)

    return ans