# Minimum Sum of Mountain Triplets I
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-sum-of-mountain-triplets-i)
Canonical: https://scaleengineer.com/dsa/problems/minimum-sum-of-mountain-triplets-i
**Data structures:** Array
---
## Problem
You are given a **0-indexed** array `nums` of integers.

A triplet of indices `(i, j, k)` is a **mountain** if:

* `i < j < k`
* `nums[i] < nums[j]` and `nums[k] < nums[j]`

Return _the **minimum possible sum** of a mountain triplet of_ `nums`. _If no such triplet exists, return_ `-1`.

**Example 1:**

**Input:** nums = [8,6,1,5,3]
**Output:** 9
**Explanation:** Triplet (2, 3, 4) is a mountain triplet of sum 9 since: 
- 2 < 3 < 4
- nums[2] < nums[3] and nums[4] < nums[3]
And the sum of this triplet is nums[2] + nums[3] + nums[4] = 9. It can be shown that there are no mountain triplets with a sum of less than 9.

**Example 2:**

**Input:** nums = [5,4,8,7,10,2]
**Output:** 13
**Explanation:** Triplet (1, 3, 5) is a mountain triplet of sum 13 since: 
- 1 < 3 < 5
- nums[1] < nums[3] and nums[5] < nums[3]
And the sum of this triplet is nums[1] + nums[3] + nums[5] = 13. It can be shown that there are no mountain triplets with a sum of less than 13.

**Example 3:**

**Input:** nums = [6,5,4,3,4,5]
**Output:** -1
**Explanation:** It can be shown that there are no mountain triplets in nums.

**Constraints:**

* `3 <= nums.length <= 50`
* `1 <= nums[i] <= 50`

# Approaches
## Brute Force
This approach directly translates the problem definition into code. It involves using three nested loops to iterate through all possible triplets of indices `(i, j, k)` such that `i < j < k`. For each triplet, it checks if it satisfies the mountain condition (`nums[i] < nums[j]` and `nums[k] < nums[j]`). If it does, the sum of the triplet's values is calculated and compared with the minimum sum found so far.
**Time:** O(n³), where n is the length of the `nums` array. The three nested loops lead to a cubic number of operations, as we check every possible triplet. · **Space:** O(1), as we only use a constant amount of extra space for variables like `minSum` and loop counters.
**Pros:** Simple to understand and implement.; Directly follows the problem statement without complex logic.
**Cons:** Highly inefficient due to its O(n³) time complexity.; Will be too slow for larger input constraints, although it passes for the given constraints (n <= 50).
### Explanation
The brute-force method is the most straightforward way to solve the problem. We systematically check every possible combination of three distinct indices `i`, `j`, and `k` that satisfy the `i < j < k` ordering. 

We can achieve this with three nested loops. The outermost loop picks the first element `nums[i]`, the middle loop picks the second element `nums[j]`, and the innermost loop picks the third element `nums[k]`. Inside the innermost loop, we have a triplet and can check if it meets the mountain criteria. If it does, we compute its sum and update our minimum sum if the current sum is smaller. We use a variable, initialized to a very large number, to keep track of this minimum sum. If, after checking all triplets, this variable hasn't changed, it means no mountain triplet exists, and we should return -1.

```java
class Solution {
    public int minimumSum(int[] nums) {
        int n = nums.length;
        int minSum = Integer.MAX_VALUE;
        boolean found = false;

        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] < nums[j] && nums[k] < nums[j]) {
                        minSum = Math.min(minSum, nums[i] + nums[j] + nums[k]);
                        found = true;
                    }
                }
            }
        }

        return found ? minSum : -1;
    }
}
```
### Algorithm
- 1. Initialize a variable `minSum` to a very large value (e.g., `Integer.MAX_VALUE`) and a boolean flag `found` to `false`.
- 2. Use a loop to iterate through each possible index `i` from `0` to `n-3`.
- 3. Inside this loop, nest another loop to iterate through each possible index `j` from `i+1` to `n-2`.
- 4. Inside the second loop, nest a third loop to iterate through each possible index `k` from `j+1` to `n-1`.
- 5. For each triplet of indices `(i, j, k)`, check if it forms a mountain: `nums[i] < nums[j]` and `nums[k] < nums[j]`.
- 6. If the condition is true, calculate the sum `currentSum = nums[i] + nums[j] + nums[k]`.
- 7. Update `minSum = Math.min(minSum, currentSum)` and set `found` to `true`.
- 8. After all loops complete, if `found` is `true`, return `minSum`. Otherwise, return -1.

## Optimized Approach by Fixing the Peak
Instead of iterating through all three indices, we can optimize by iterating through the middle index `j` (the peak) and then finding the best possible `i` and `k`. For a fixed `j`, to minimize the sum `nums[i] + nums[j] + nums[k]`, we need to find the smallest `nums[i]` to its left (where `i < j` and `nums[i] < nums[j]`) and the smallest `nums[k]` to its right (where `k > j` and `nums[k] < nums[j]`).
**Time:** O(n²), where n is the length of the array. The main loop runs `n-2` times for `j`. Inside it, we perform two scans (one to the left, one to the right) that take O(j) and O(n-j) time respectively, leading to an overall O(n) work per `j`. · **Space:** O(1), as we only use a constant amount of extra space for variables.
**Pros:** Significantly more efficient than the O(n³) brute-force approach.; Still relatively easy to reason about and implement.; Requires no extra space.
**Cons:** The repeated scanning for `minLeft` and `minRight` for each `j` is redundant work.; While better than O(n³), it's not the most optimal solution.
### Explanation
This approach improves upon the brute-force method by changing the iteration strategy. We fix the middle element of the potential triplet, `nums[j]`, which acts as the peak of the mountain. The index `j` can range from `1` to `n-2`.

For each `j`, our goal is to find an `i < j` and a `k > j` such that `nums[i]` and `nums[k]` are both smaller than `nums[j]`, and their sum is minimized. This is achieved by finding the absolute minimum element to the left of `j` that is smaller than `nums[j]`, and the absolute minimum element to the right of `j` that is also smaller than `nums[j]`. 

We can find these two minimums by performing two separate linear scans for each `j`: one from `0` to `j-1` and another from `j+1` to `n-1`. If we find valid minimums on both sides, we form a triplet, calculate its sum, and update the global minimum sum.

```java
class Solution {
    public int minimumSum(int[] nums) {
        int n = nums.length;
        int minSum = Integer.MAX_VALUE;

        for (int j = 1; j < n - 1; j++) {
            int minLeft = Integer.MAX_VALUE;
            for (int i = 0; i < j; i++) {
                if (nums[i] < nums[j]) {
                    minLeft = Math.min(minLeft, nums[i]);
                }
            }

            int minRight = Integer.MAX_VALUE;
            for (int k = j + 1; k < n; k++) {
                if (nums[k] < nums[j]) {
                    minRight = Math.min(minRight, nums[k]);
                }
            }

            if (minLeft != Integer.MAX_VALUE && minRight != Integer.MAX_VALUE) {
                minSum = Math.min(minSum, minLeft + nums[j] + minRight);
            }
        }

        return minSum == Integer.MAX_VALUE ? -1 : minSum;
    }
}
```
### Algorithm
- 1. Initialize `minSum` to `Integer.MAX_VALUE`.
- 2. Iterate through each possible peak index `j` from `1` to `n-2`.
- 3. For each `j`, initialize `minLeft` and `minRight` to `Integer.MAX_VALUE`.
- 4. Find the minimum element to the left of `j`: Iterate `i` from `0` to `j-1`. If `nums[i] < nums[j]`, update `minLeft = min(minLeft, nums[i])`.
- 5. Find the minimum element to the right of `j`: Iterate `k` from `j+1` to `n-1`. If `nums[k] < nums[j]`, update `minRight = min(minRight, nums[k])`.
- 6. If both `minLeft` and `minRight` were updated (i.e., are not `Integer.MAX_VALUE`), it means a valid mountain can be formed with `j` as the peak.
- 7. Calculate the sum `minLeft + nums[j] + minRight` and update `minSum = min(minSum, ...)`.
- 8. After the main loop, if `minSum` is still `Integer.MAX_VALUE`, return -1. Otherwise, return `minSum`.

## Linear Time Solution with Precomputation
This is the most efficient approach. It builds upon the O(n²) idea but avoids the repeated scans by precomputing the minimum values. We can create two auxiliary arrays: `prefixMin` and `suffixMin`. `prefixMin[i]` stores the minimum value in `nums[0...i]`, and `suffixMin[i]` stores the minimum value in `nums[i...n-1]`. After a one-time O(n) computation for these arrays, we can find the minimum left and right elements for any peak `j` in O(1) time.
**Time:** O(n), where n is the length of the array. We make three separate passes through the array (one for `prefixMin`, one for `suffixMin`, and one for the final calculation), each taking O(n) time. The total time is O(n) + O(n) + O(n) = O(n). · **Space:** O(n), for the `prefixMin` and `suffixMin` arrays, each of size `n`.
**Pros:** Highly efficient with a linear time complexity, making it the optimal solution.; The logic is a clear optimization of the previous approach.
**Cons:** Requires extra space proportional to the input size for the precomputation arrays.
### Explanation
To achieve a linear time solution, we can eliminate the repetitive work done in the O(n²) approach. The bottleneck was finding the minimum element to the left and right of each potential peak `j`. This can be optimized by precomputing these values.

We use two auxiliary arrays:
1. `prefixMin`: `prefixMin[i]` will store the minimum value in the subarray `nums[0...i]`. This can be computed in a single pass from left to right.
2. `suffixMin`: `suffixMin[i]` will store the minimum value in the subarray `nums[i...n-1]`. This can be computed in a single pass from right to left.

After these two arrays are populated, we can iterate through each potential peak `j` from `1` to `n-2`. For any `j`, the minimum element in `nums[0...j-1]` is simply `prefixMin[j-1]`, and the minimum element in `nums[j+1...n-1]` is `suffixMin[j+1]`. We can access these in O(1) time. We then check if these minimums are less than `nums[j]` to form a mountain, and if so, update our global minimum sum.

```java
class Solution {
    public int minimumSum(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return -1;
        }

        int[] prefixMin = new int[n];
        prefixMin[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefixMin[i] = Math.min(prefixMin[i - 1], nums[i]);
        }

        int[] suffixMin = new int[n];
        suffixMin[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suffixMin[i] = Math.min(suffixMin[i + 1], nums[i]);
        }

        int minSum = Integer.MAX_VALUE;
        for (int j = 1; j < n - 1; j++) {
            int leftMin = prefixMin[j - 1];
            int rightMin = suffixMin[j + 1];
            if (leftMin < nums[j] && rightMin < nums[j]) {
                minSum = Math.min(minSum, leftMin + nums[j] + rightMin);
            }
        }

        return minSum == Integer.MAX_VALUE ? -1 : minSum;
    }
}
```
### Algorithm
- 1. Create a `prefixMin` array of size `n`. Initialize `prefixMin[0] = nums[0]`.
- 2. Fill the `prefixMin` array by iterating from `i = 1` to `n-1`, setting `prefixMin[i] = min(prefixMin[i-1], nums[i])`.
- 3. Create a `suffixMin` array of size `n`. Initialize `suffixMin[n-1] = nums[n-1]`.
- 4. Fill the `suffixMin` array by iterating from `i = n-2` down to `0`, setting `suffixMin[i] = min(suffixMin[i+1], nums[i])`.
- 5. Initialize `minSum` to `Integer.MAX_VALUE`.
- 6. Iterate through the potential peak index `j` from `1` to `n-2`.
- 7. For each `j`, get the minimum element to its left as `leftMin = prefixMin[j-1]` and the minimum to its right as `rightMin = suffixMin[j+1]`.
- 8. Check if a mountain can be formed: `leftMin < nums[j]` and `rightMin < nums[j]`.
- 9. If true, update `minSum = min(minSum, leftMin + nums[j] + rightMin)`.
- 10. After the loop, if `minSum` is `Integer.MAX_VALUE`, return -1. Otherwise, return `minSum`.

# Solutions
### Java

```java
class Solution {
public
  int minimumSum(int[] nums) {
    int n = nums.length;
    int[] right = new int[n + 1];
    final int inf = 1 << 30;
    right[n] = inf;
    for (int i = n - 1; i >= 0; --i) {
      right[i] = Math.min(right[i + 1], nums[i]);
    }
    int ans = inf, left = inf;
    for (int i = 0; i < n; ++i) {
      if (left < nums[i] && right[i + 1] < nums[i]) {
        ans = Math.min(ans, left + nums[i] + right[i + 1]);
      }
      left = Math.min(left, nums[i]);
    }
    return ans == inf ? -1 : ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumSum(vector<int> &nums) {
    int n = nums.size();
    const int inf = 1 << 30;
    int right[n + 1];
    right[n] = inf;
    for (int i = n - 1; ~i; --i) {
      right[i] = min(right[i + 1], nums[i]);
    }
    int ans = inf, left = inf;
    for (int i = 0; i < n; ++i) {
      if (left < nums[i] && right[i + 1] < nums[i]) {
        ans = min(ans, left + nums[i] + right[i + 1]);
      }
      left = min(left, nums[i]);
    }
    return ans == inf ? -1 : ans;
  }
};

```

### Python

```python
class Solution:
    def minimumSum(self, nums: List[int]) -> int: n = len(nums) right = [inf] * (n + 1) for i in range(n - 1, - 1, - 1): right[i] = min(right[i + 1], nums[i]) ans = left = inf for i, x in enumerate(nums): if left < x and right[i + 1] < x: ans = min(ans, left + x + right[i + 1]) left = min(left, x) return - 1 if ans == inf else ans

```