🌱 Keegan's Digital Garden

1130. Minimum Cost Tree From Leaf Values

3 min read

📝 Problem Details

💭What Were My Initial Thoughts?

- The question seems misleading initially, as it suggests constructing all possible binary trees. 

- My initial thoughts were to explicitly compute all possible tree structures to find the one with the minimum cost. - However, that approach would be computationally infeasible for larger inputs. 

- I realized that we don't need to explicitly construct the tree but rather treat it as a mathematical problem involving optimal grouping of elements.

🤔What Did I Struggle With?

- Understanding how to approach the problem without explicitly constructing the tree.
- How to efficiently compute the costs of merging leaf nodes without trying all possible combinations.
- How to manage adjacent elements dynamically as the array evolves during merges (solved using a stack).

💡 Explanation of Solution

Key Idea:

We can solve the problem without constructing the tree by leveraging a greedy strategy with a monotonic stack:

  1. Treat the problem as finding the optimal pairs of adjacent leaves to merge, minimizing the sum of non-leaf node values.
  2. The product of two adjacent leaves becomes a non-leaf node. Minimize the cost by always merging the smaller leaf with its neighbor first.

Algorithm:

1. Use a stack to maintain a monotonic decreasing sequence of elements.

2. As we traverse the array:
   - If the current element is greater than or equal to the top of the stack, merge the top element with the smaller of its two neighbors (either the next value or the second-to-top element in the stack).
   - Continue merging until the stack maintains a decreasing order.

3. After traversing the array, merge the remaining elements in the stack pairwise.

Why Does This Work?

The stack ensures that we always merge the smallest elements early, minimizing the cost of non-leaf nodes. By greedily merging adjacent leaves based on this rule, we avoid unnecessary computations and guarantee the optimal result.

⌛ Complexity Analysis

Time Complexity: O(n)
- the input array is traversed once, each element is pushed and popped from the stack exactly once
- pushed once: only when it is encountered in the array
- popped once: when the current value is greater than or equal to it
	- it never goes back into the stack because its role in a merge has been completed

Space Complexity: O(n) for the construction of the stack with N elements

💻 Implementation of Solution

class Solution {
public:
    int mctFromLeafValues(vector<int>& arr) {
        stack<int> stk;
        int result = 0;
 
        for(int i=0; i < arr.size(); i++) {
            while(!stk.empty() && stk.top() <= arr[i]) {
                int mid = stk.top();
                stk.pop();
 
                int left = stk.empty() ? INT_MAX : stk.top(); //second to top element
                result += mid * min(left, arr[i]);
            }
            stk.push(arr[i]);
        }
 
        while(stk.size() > 1) {
            int top = stk.top();
            stk.pop();
 
            result += top * stk.top();
        }
 
        return result;
    }
};

Graph View