# 1130. Minimum Cost Tree From Leaf Values

<figure><img src="/files/0HR7tBp5aTKDzpJZXd01" alt=""><figcaption></figcaption></figure>

T: O(n^2), every round finds the smallest index(from n numbers), then count pre, post, and do n times. so n^2

S: O(n), removeElement needs n space to copy

````java
```java
class Solution {
    public int mctFromLeafValues(int[] A) {
        int res = 0;
        while (A.length > 1) {
            int i = indexOfMin(A);
            if (i == A.length-1) {
                res += A[i-1] * A[i];
            } else if (i == 0) {
                res += A[i+1] * A[i];
            } else {
                res += Math.min(A[i-1], A[i+1]) * A[i];
            }
            A = removeElement(A, i);
        }
        return res;
    }

    public int indexOfMin(int[] A) {
        int minIndex = 0;
        for (int i = 1; i < A.length; i++) {
            if (A[i] < A[minIndex]) {
                minIndex = i;
            }
        }
        return minIndex;
    }

    public int[] removeElement(int[] A, int index) {
        int[] newArray = new int[A.length - 1];
        System.arraycopy(A, 0, newArray, 0, index);
        System.arraycopy(A, index + 1, newArray, index, A.length - index - 1);
        return newArray;
    }
}
```
````

## Mono Stack

T: O(n)

S: O(n)

````java
```java
class Solution {
    public int mctFromLeafValues(int[] arr) {
        int[] nextGreater = nextGreater(arr);
        int[] prevGreater = prevGreater(arr);

        int result = 0;
        for (int i = 0; i < arr.length; i++) {
            // if nextGreater and prevGreater are both Integer.MAX_VALUE which means no need to cal, means this number is the biggest in the array
            if (nextGreater[i] != Integer.MAX_VALUE || prevGreater[i] != Integer.MAX_VALUE) {
                result += arr[i]*Math.min(nextGreater[i], prevGreater[i]);
            }
        }
        return result;
    }
    private int[] nextGreater(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        Arrays.fill(result, Integer.MAX_VALUE);
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[i] >= arr[stack.peek()]) {
                result[stack.pop()] = arr[i];
            }
            stack.push(i);
        }
        return result;
    }
    private int[] prevGreater(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        Arrays.fill(result, Integer.MAX_VALUE);
        Stack<Integer> stack = new Stack<>();
        for (int i = n-1; i >= 0; i--) {
            while (!stack.isEmpty() && arr[i] > arr[stack.peek()]) {
                result[stack.pop()] = arr[i];
            }
            stack.push(i);
        }
        return result;
    }
}

/*


[6,2,4]
we should remain bigger one until last

8

6, 4

24


x3 x2. x1 x4 (x5)

[1, 0, 3, 4]

if we want to remove 1,
if 1, 0 merge -> 1 still here, so we should choose bigger neighbor

[2, 1, 0, 3, 4]

1* min(2, 3)
     c
  a. c 
 xa bc 
xxa bc



our goal: 
keep remove small one, at last remain biggest

in this way, we can get min cost

if we choose removing bigger one, this bigger one still remain in next iteration, the cost will be higher

choose 2 number
a*b where b >= a

min cost is a*b
a already small one, so the key is b
b can be from a's left or right bigger neighbor (b >= a) (and first one, because it's more close)
and for better b, it's min(left_b, right_b)

so the ans is a* min(left_b, right_b)

how do we know left_b, right_b ? cal nextGreater and prevGreater


equal case need to include = (in one side, here I choose next Greater has =, but prevGreater doesn't have =)


*/
```ja
````


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/stack/mono-stack/1130.-minimum-cost-tree-from-leaf-values.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.