1130. Minimum Cost Tree From Leaf Values

https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/

O(N^2) Solution

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        res = 0
        while len(arr) > 1:
            i = arr.index(min(arr))
            res += arr[i] * min(arr[i-1:i] + arr[i+1:i+2])
            arr.pop(i)
        return res

O(N) Use decreasing stack

left next greater and right next greater

stack: [7,6,5,4,5]

res += mid * min(leftGreater, rightGreater) = 4 * min(5,5)

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        stack = [float("inf")]
        res = 0
        for num in arr:
            while stack and stack[-1] <= num:
                mid = stack.pop()
                res += min(stack[-1],num) * mid
            stack.append(num)
        
        while len(stack) > 2:
            res += stack.pop() * stack[-1]
        return res