Minimum Cost Tree From Leaf Values

LeetCode problem #1130

Language Selection

Choose your preferred programming language

Showing: Python

Problem Statement

You are given an integer array arr of positive integers, where each element represents a leaf value.

We want to build a full binary tree (every node has either 0 or 2 children) such that:

  • The leaves, read from left to right, are exactly the values in arr (in the same order).
  • Each non-leaf node has a value equal to:
    • max(leaf values in its left subtree) * max(leaf values in its right subtree)
  • The cost of the tree is the sum of all non-leaf node values.

Return the minimum possible cost among all valid full binary trees.

Input / Output Format

  • Input: arr — array of integers (int[])
  • Output: an integer — the minimum sum of non-leaf node values

Constraints

  • 2 <= arr.length <= 40
  • 1 <= arr[i] <= 15
  • Answer fits in a 32-bit signed integer.

Examples

Example 1

Input: arr = [6,2,4]
Output: 32

Explanation: Possible trees (conceptually via partitioning):

  • Split as [6] | [2,4]
    • Left max = 6
    • Right subtree best for [2,4] has cost 2*4=8 and max = 4
    • Root cost = 6*4=24
    • Total = 8 + 24 = 32 This is minimal.

Example 2

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

Explanation: Only one tree: 4 and 11 as leaves. Cost = 4*11 = 44.

Example 3 (classic)

Input: arr = [7,12,8,10]
Output: 284

Explanation (one optimal structure): A minimal-cost combination ends up pairing smaller maxima earlier and avoiding multiplying large maxima repeatedly. The optimized monotonic-stack solution yields 284.

Edge Example

Input: arr = [1,1,1,1]
Output: 3

Explanation: Any merge costs 1*1=1. There are n-1 = 3 internal nodes, total cost 3.

Approach 1: Brute Force (DP over intervals)

Idea

This problem has an optimal substructure when you consider building a tree from a contiguous subarray arr[i..j].

If we choose a split point k (i <= k < j), then:

  • Left subtree uses leaves arr[i..k]
  • Right subtree uses leaves arr[k+1..j]
  • The root value contributed by this split is:
    • max(arr[i..k]) * max(arr[k+1..j])

So we can compute:

dp[i][j] = min over k: dp[i][k] + dp[k+1][j] + max(i..k) * max(k+1..j)

We precompute max(i..j) for all intervals to make transitions fast.

Complexity

  • Precompute maxima: O(n^2)
  • DP transitions: O(n^3) (for each interval, try all splits)
  • Space: O(n^2)
  • With n <= 40, this is acceptable.

Brute Force Code

Python:

from typing import List

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        if arr is None or len(arr) < 2:
            return 0

        n = len(arr)
        mx = [[0] * n for _ in range(n)]
        for i in range(n):
            mx[i][i] = arr[i]
            for j in range(i + 1, n):
                mx[i][j] = max(mx[i][j - 1], arr[j])

        INF = 10**18
        dp = [[0] * n for _ in range(n)]
        for length in range(2, n + 1):
            for i in range(0, n - length + 1):
                j = i + length - 1
                best = INF
                for k in range(i, j):
                    cost = dp[i][k] + dp[k + 1][j] + mx[i][k] * mx[k + 1][j]
                    if cost < best:
                        best = cost
                dp[i][j] = best

        return dp[0][n - 1]

Java:

import java.util.*;

class Solution {
    public int mctFromLeafValues(int[] arr) {
        if (arr == null || arr.length < 2) return 0;

        int n = arr.length;
        int[][] mx = new int[n][n];
        for (int i = 0; i < n; i++) {
            mx[i][i] = arr[i];
            for (int j = i + 1; j < n; j++) {
                mx[i][j] = Math.max(mx[i][j - 1], arr[j]);
            }
        }

        int[][] dp = new int[n][n];
        final int INF = Integer.MAX_VALUE / 4;

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                int best = INF;
                for (int k = i; k < j; k++) {
                    int cost = dp[i][k] + dp[k + 1][j] + mx[i][k] * mx[k + 1][j];
                    if (cost < best) best = cost;
                }
                dp[i][j] = best;
            }
        }
        return dp[0][n - 1];
    }
}

Go:

package main

func mctFromLeafValues(arr []int) int {
	if arr == nil || len(arr) < 2 {
		return 0
	}
	n := len(arr)

	mx := make([][]int, n)
	for i := range mx {
		mx[i] = make([]int, n)
		mx[i][i] = arr[i]
		for j := i + 1; j < n; j++ {
			if mx[i][j-1] > arr[j] {
				mx[i][j] = mx[i][j-1]
			} else {
				mx[i][j] = arr[j]
			}
		}
	}

	const INF = int(^uint(0) >> 1) / 4
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
	}

	for length := 2; length <= n; length++ {
		for i := 0; i+length-1 < n; i++ {
			j := i + length - 1
			best := INF
			for k := i; k < j; k++ {
				cost := dp[i][k] + dp[k+1][j] + mx[i][k]*mx[k+1][j]
				if cost < best {
					best = cost
				}
			}
			dp[i][j] = best
		}
	}

	return dp[0][n-1]
}

JavaScript:

/**
 * @param {number[]} arr
 * @return {number}
 */
function mctFromLeafValues(arr) {
  if (!Array.isArray(arr) || arr.length < 2) return 0;

  const n = arr.length;
  const mx = Array.from({ length: n }, () => Array(n).fill(0));
  for (let i = 0; i < n; i++) {
    mx[i][i] = arr[i];
    for (let j = i + 1; j < n; j++) {
      mx[i][j] = Math.max(mx[i][j - 1], arr[j]);
    }
  }

  const dp = Array.from({ length: n }, () => Array(n).fill(0));
  const INF = Number.MAX_SAFE_INTEGER;

  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      let best = INF;
      for (let k = i; k < j; k++) {
        const cost = dp[i][k] + dp[k + 1][j] + mx[i][k] * mx[k + 1][j];
        if (cost < best) best = cost;
      }
      dp[i][j] = best;
    }
  }

  return dp[0][n - 1];
}

C#:

using System;

public class Solution {
    public int mctFromLeafValues(int[] arr) {
        if (arr == null || arr.Length < 2) return 0;

        int n = arr.Length;
        int[,] mx = new int[n, n];
        for (int i = 0; i < n; i++) {
            mx[i, i] = arr[i];
            for (int j = i + 1; j < n; j++) {
                mx[i, j] = Math.Max(mx[i, j - 1], arr[j]);
            }
        }

        int[,] dp = new int[n, n];
        int INF = int.MaxValue / 4;

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                int best = INF;
                for (int k = i; k < j; k++) {
                    int cost = dp[i, k] + dp[k + 1, j] + mx[i, k] * mx[k + 1, j];
                    if (cost < best) best = cost;
                }
                dp[i, j] = best;
            }
        }

        return dp[0, n - 1];
    }
}

Approach 2: Optimized Solution (Monotonic Stack, Greedy)

Key Idea

A well-known greedy insight: to minimize total cost, you want to avoid multiplying large leaf values multiple times. The optimal strategy is equivalent to repeatedly removing a leaf and paying:

leaf * min(nearest greater on left, nearest greater on right)

This can be implemented using a monotonic decreasing stack:

  • Maintain a stack of decreasing values.
  • When you see a value x that is >= stack top, pop mid = stack top.
  • The cost contribution is mid * min(new stack top, x) (the smaller neighbor among the two “greater-or-equal boundaries”).
  • At the end, collapse the stack by multiplying adjacent elements.

This produces the minimum cost in O(n) time.

Complexity

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

Optimized Code (Monotonic Stack)

Python:

from typing import List

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        if arr is None or len(arr) < 2:
            return 0

        res = 0
        stack = [float("inf")]  # sentinel to avoid empty checks

        for x in arr:
            while stack and x >= stack[-1]:
                mid = stack.pop()
                res += mid * min(stack[-1], x)
            stack.append(x)

        while len(stack) > 2:
            mid = stack.pop()
            res += mid * stack[-1]

        return int(res)

Java:

import java.util.*;

class Solution {
    public int mctFromLeafValues(int[] arr) {
        if (arr == null || arr.length < 2) return 0;

        int res = 0;
        Deque<Integer> st = new ArrayDeque<>();
        st.push(Integer.MAX_VALUE); // sentinel

        for (int x : arr) {
            while (st.peek() != null && x >= st.peek()) {
                int mid = st.pop();
                res += mid * Math.min(st.peek(), x);
            }
            st.push(x);
        }

        while (st.size() > 2) {
            int mid = st.pop();
            res += mid * st.peek();
        }

        return res;
    }
}

Go:

package main

import "math"

func mctFromLeafValuesOptimized(arr []int) int {
	if arr == nil || len(arr) < 2 {
		return 0
	}

	res := 0
	stack := make([]int, 0, len(arr)+1)
	stack = append(stack, int(math.MaxInt32)) // sentinel

	for _, x := range arr {
		for len(stack) > 0 && x >= stack[len(stack)-1] {
			mid := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			left := stack[len(stack)-1]
			if left < x {
				res += mid * left
			} else {
				res += mid * x
			}
		}
		stack = append(stack, x)
	}

	for len(stack) > 2 {
		mid := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		res += mid * stack[len(stack)-1]
	}

	return res
}

JavaScript:

/**
 * @param {number[]} arr
 * @return {number}
 */
function mctFromLeafValues(arr) {
  if (!Array.isArray(arr) || arr.length < 2) return 0;

  let res = 0;
  const st = [Number.POSITIVE_INFINITY]; // sentinel

  for (const x of arr) {
    while (x >= st[st.length - 1]) {
      const mid = st.pop();
      res += mid * Math.min(st[st.length - 1], x);
    }
    st.push(x);
  }

  while (st.length > 2) {
    const mid = st.pop();
    res += mid * st[st.length - 1];
  }

  return res;
}

C#:

using System;
using System.Collections.Generic;

public class Solution {
    public int mctFromLeafValues(int[] arr) {
        if (arr == null || arr.Length < 2) return 0;

        int res = 0;
        var st = new Stack<int>();
        st.Push(int.MaxValue); // sentinel

        foreach (int x in arr) {
            while (st.Count > 0 && x >= st.Peek()) {
                int mid = st.Pop();
                int left = st.Peek(); // safe due to sentinel
                res += mid * Math.Min(left, x);
            }
            st.Push(x);
        }

        while (st.Count > 2) {
            int mid = st.Pop();
            res += mid * st.Peek();
        }

        return res;
    }
}

Key Insights

  • DP interval splitting models the exact problem definition and is a safe baseline.
  • The monotonic decreasing stack solution is a greedy optimization:
    • Every leaf value (except the global maximum) must be multiplied exactly once with a “next larger neighbor” to form internal nodes.
    • When a value mid is popped, its two candidates to pair with are the nearest greater values on left and right; pairing with the smaller of those minimizes cost.
  • The stack ensures each element is pushed/popped at most once → linear time.

Edge Cases

  • arr.length == 2 → answer is arr[0] * arr[1]
  • All equal values: [k,k,k,...] → cost = (n-1) * k*k
  • Strictly increasing: [1,2,3,4] (many pops)
  • Strictly decreasing: [4,3,2,1] (few pops, mostly final collapse)
  • Repeated peaks: [6,2,4,7,3]
  • Input validation: null / empty / length < 2 (return 0 in implementations)

Test Cases

Python:

def test():
    s = Solution()
    assert s.mctFromLeafValues([6,2,4]) == 32
    assert s.mctFromLeafValues([4,11]) == 44
    assert s.mctFromLeafValues([1,1,1,1]) == 3
    assert s.mctFromLeafValues([7,12,8,10]) == 284
    assert s.mctFromLeafValues([3,2]) == 6
    print("OK")

# test()

Java:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        if (s.mctFromLeafValues(new int[]{6,2,4}) != 32) throw new RuntimeException("fail");
        if (s.mctFromLeafValues(new int[]{4,11}) != 44) throw new RuntimeException("fail");
        if (s.mctFromLeafValues(new int[]{1,1,1,1}) != 3) throw new RuntimeException("fail");
        if (s.mctFromLeafValues(new int[]{7,12,8,10}) != 284) throw new RuntimeException("fail");
        if (s.mctFromLeafValues(new int[]{3,2}) != 6) throw new RuntimeException("fail");
        System.out.println("OK");
    }
}

Go:

package main

import "testing"

func TestMCT(t *testing.T) {
	tests := []struct {
		arr  []int
		want int
	}{
		{[]int{6, 2, 4}, 32},
		{[]int{4, 11}, 44},
		{[]int{1, 1, 1, 1}, 3},
		{[]int{7, 12, 8, 10}, 284},
		{[]int{3, 2}, 6},
	}

	for _, tc := range tests {
		got := mctFromLeafValuesOptimized(tc.arr)
		if got != tc.want {
			t.Fatalf("arr=%v got=%d want=%d", tc.arr, got, tc.want)
		}
	}
}

Common Mistakes

  • Forgetting the “leaves in-order must match arr” and trying to reorder values.
  • In DP:
    • Not precomputing maxima → slow code or repeated max() calls.
    • Off-by-one errors in interval loops.
  • In stack approach:
    • Missing the sentinel and causing empty-stack errors.
    • Using > instead of >= (can break correctness with duplicates).
    • Forgetting the final collapse step (remaining decreasing stack).
  • Integer overflow concerns:
    • In these constraints, 32-bit is safe, but using safe sentinels and avoiding MAX_VALUE * something is important (the sentinel is never multiplied).

Interview Tips

  • Start with the DP interval solution:
    • Define dp[i][j] clearly and write the recurrence.
    • Mention n <= 40, so O(n^3) is acceptable.
  • Then propose the optimized greedy:
    • Explain the intuition: each leaf (except max) is multiplied once with the closest larger neighbor; choose the smaller larger neighbor to minimize cost.
    • Use a monotonic decreasing stack to find “next greater on both sides” implicitly.
  • Be ready to walk through [6,2,4] step-by-step on the stack to demonstrate confidence.
  • Call out complexity improvements: from O(n^3) to O(n) and why correctness still holds.