Minimum Cost Tree From Leaf Values

MediumStackmonotonic stack

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given an array arr of positive integers, consider every binary tree where: - every node has either 0 or 2 children, - the leaves, read left to right in an in-order traversal, are exactly the values of arr, - each internal node's value is the product of the **largest leaf in its left subtree** and the **largest leaf in its right subtree**. Return the smallest possible sum of the internal node values over all such trees. The answer fits in a 32-bit signed integer.

Examples

Input: arr = [6,2,4]
Output: 32
Pairing 2 and 4 first costs 8, then 6 with the max of (2,4) costs 24: total 32. Pairing 6 and 2 first would cost 12 + 24 = 36.
Input: arr = [4,11]
Output: 44
A single internal node with value 4 * 11.

Constraints

  • `2 <= arr.length <= 40`
  • `1 <= arr[i] <= 15`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More monotonic stack problems