#
# @lc app=leetcode id=1130 lang=python3
#
# [1130] Minimum Cost Tree From Leaf Values
#
# https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/description/
#
# algorithms
# Medium (63.05%)
# Total Accepted:    12.4K
# Total Submissions: 19.6K
# Testcase Example:  '[6,2,4]'
#
# 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.  (Recall that a node is a leaf if and only if it has 0
# children.)
# 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.
# 
# 
# Example 1:
# 
# 
# Input: arr = [6,2,4]
# Output: 32
# Explanation:
# There are two possible trees.  The first has non-leaf node sum 36, and the
# second has non-leaf node sum 32.
# 
# ⁠   24            24
# ⁠  /  \          /  \
# ⁠ 12   4        6    8
# ⁠/  \               / \
# 6    2             2   4
# 
# 
# 
# Constraints:
# 
# 
# 2 <= arr.length <= 40
# 1 <= arr[i] <= 15
# It is guaranteed that the answer fits into a 32-bit signed integer (ie. it is
# less than 2^31).
# 
#
class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        res = 0
        while len(arr) > 1:
            mini_idx = arr.index(min(arr))
            if 0 < mini_idx < len(arr) - 1:
                res += min(arr[mini_idx - 1], arr[mini_idx + 1]) * arr[mini_idx]
            else:
                res += arr[1 if mini_idx == 0 else mini_idx - 1] * arr[mini_idx]
            arr.pop(mini_idx)
        return res
        
s = Solution()
arr = [7, 12, 8, 10]
arr = [3,7,2,12,15,10,3,9]
print(s.mctFromLeafValues(arr))


