LC-1130 Medium LeetCode

1130. Minimum Cost Tree From Leaf Values

Array Dynamic Programming Stack Greedy Monotonic Stack

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 68% Topics: Array, Dynamic Programming, Stack, Greedy, Monotonic Stack

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min Stacks & Queues 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

class Solution(object):
    def mctFromLeafValues(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        result = 0
        stk = [float("inf")]
        for x in arr:
            while stk[-1] <= x:
                result += stk.pop() * min(stk[-1], x)
            stk.append(x)
        while len(stk) > 2:
            result += stk.pop() * stk[-1]
        return result

Solution from kamyu104/LeetCode-Solutions · MIT