# Minimum Sum of Mountain Triplets II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-sum-of-mountain-triplets-ii)
Canonical: https://scaleengineer.com/dsa/problems/minimum-sum-of-mountain-triplets-ii
**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 <= 105`
* `1 <= nums[i] <= 108`

# Approaches
## Brute Force Enumeration
This approach involves checking every possible triplet of indices `(i, j, k)` to see if it forms a mountain triplet. It's the most straightforward but also the least efficient method, serving as a baseline.
**Time:** O(n³), where n is the number of elements in `nums`. The three nested loops lead to a cubic time complexity, which is too slow for the problem's constraints (`n <= 10^5`). · **Space:** O(1), as we only use a few variables to store the minimum sum and loop indices.
**Pros:** Simple to understand and implement.; Correct for small input sizes.
**Cons:** Extremely inefficient due to its cubic time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
### Explanation
We use three nested loops to generate all combinations of `i`, `j`, and `k` such that `0 <= i < j < k < n`, where `n` is the length of the array. For each triplet, we check if it satisfies the mountain conditions: `nums[i] < nums[j]` and `nums[k] < nums[j]`. If the conditions are met, we calculate the sum `nums[i] + nums[j] + nums[k]`. We keep track of the minimum sum found so far. If after checking all triplets, no mountain triplet has been found, we return -1. Otherwise, we return the minimum sum.

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

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

        return found ? (int)minSum : -1;
    }
}
```
### Algorithm
*   Initialize `minSum` to a very large value (e.g., `Long.MAX_VALUE`).
*   Use a first loop to iterate through index `i` from `0` to `n-3`.
*   Inside, use a second loop to iterate through index `j` from `i+1` to `n-2`.
*   Inside the second loop, use a third loop to iterate through index `k` from `j+1` to `n-1`.
*   In the innermost loop, check if the triplet `(i, j, k)` forms a mountain: `nums[i] < nums[j]` and `nums[k] < nums[j]`.
*   If it is a mountain, calculate the sum `nums[i] + nums[j] + nums[k]` and update `minSum` with the minimum value seen so far.
*   After all loops complete, if `minSum` remains at its initial large value, no mountain triplet was found, so return -1.
*   Otherwise, return the `minSum`.

## Optimized Iteration by Fixing the Peak
Instead of three nested loops, we can improve the logic by fixing the middle element `nums[j]` (the peak of the mountain) and then searching for the best possible left (`nums[i]`) and right (`nums[k]`) elements for it. This reduces the complexity from cubic to quadratic.
**Time:** O(n²), where n is the number of elements. The main loop runs O(n) times, and inside it, the two searches take O(j) and O(n-j) time, leading to an overall quadratic complexity. · **Space:** O(1), as we only use a constant amount of extra space for variables.
**Pros:** More efficient than the O(n³) brute-force approach.; Maintains a simple structure with constant extra space.
**Cons:** Still inefficient for large inputs and will likely time out.; Performs redundant computations by repeatedly scanning the left and right subarrays for each potential peak.
### Explanation
We iterate through the array with a main loop for index `j` from `1` to `n-2`. For each `nums[j]`, we treat it as a potential peak. Then, we perform two separate searches: one to its left and one to its right. We search the subarray `nums[0...j-1]` for the minimum element that is less than `nums[j]`. We do the same for the subarray `nums[j+1...n-1]`. If we find such minimums on both sides, we form a triplet and update our global minimum sum. This avoids the third nested loop of the pure brute-force approach.

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

        for (int j = 1; j < n - 1; j++) {
            int minLeft = Integer.MAX_VALUE;
            int minRight = Integer.MAX_VALUE;
            
            // Find minimum on the left
            for (int i = 0; i < j; i++) {
                if (nums[i] < nums[j]) {
                    minLeft = Math.min(minLeft, nums[i]);
                }
            }

            // Find minimum on the right
            if (minLeft != 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, (long)minLeft + nums[j] + minRight);
            }
        }

        return minSum == Long.MAX_VALUE ? -1 : (int)minSum;
    }
}
```
### Algorithm
*   Initialize `minSum` to a very large value.
*   Iterate through the array with an index `j` from `1` to `n-2`, considering `nums[j]` as the peak of a potential mountain.
*   For each `j`, initialize `minLeft` and `minRight` to a large value.
*   In a nested loop, iterate `i` from `0` to `j-1`. If `nums[i] < nums[j]`, update `minLeft = Math.min(minLeft, nums[i])`.
*   In another nested loop, iterate `k` from `j+1` to `n-1`. If `nums[k] < nums[j]`, update `minRight = Math.min(minRight, nums[k])`.
*   If both a valid `minLeft` and `minRight` were found, calculate the sum `minLeft + nums[j] + minRight` and update the overall `minSum`.
*   After the main loop, if `minSum` is unchanged, return -1. Otherwise, return `minSum`.

## Linear Time Solution using Precomputation
The O(n²) approach is slow because finding the minimums to the left and right of each element `j` is done repeatedly. We can optimize this to a linear time solution by precomputing these minimums. This allows us to find the minimum sum in a single pass over the potential peaks.
**Time:** O(n). We make three separate passes through the array: one to compute `prefixMin`, one for `suffixMin`, and one to find the minimum sum. Each pass takes O(n) time, making the total O(n). · **Space:** O(n), as we use two additional arrays, `prefixMin` and `suffixMin`, each of size `n`.
**Pros:** Highly efficient with an optimal time complexity.; Guaranteed to pass within the time limits for the given constraints.
**Cons:** Uses extra space proportional to the input size for the precomputed arrays.
### Explanation
The key insight is that for any potential peak `nums[j]`, the best possible left element `nums[i]` will always be the minimum value in the entire prefix `nums[0...j-1]`. Similarly, the best right element `nums[k]` will be the minimum in the suffix `nums[j+1...n-1]`. We can precompute all prefix minimums and all suffix minimums in O(n) time.

First, we create a `prefixMin` array where `prefixMin[i]` stores `min(nums[0]...nums[i])`. Then, we create a `suffixMin` array where `suffixMin[i]` stores `min(nums[i]...nums[n-1])`. With these arrays, we can iterate through `j` from `1` to `n-2`. For each `j`, we can find the left and right minimums in O(1) time by looking up `prefixMin[j-1]` and `suffixMin[j+1]`. We check if they form a mountain with `nums[j]` and update the minimum sum accordingly.

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

        // prefixMin[i] = min(nums[0]...nums[i])
        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]);
        }

        // suffixMin[i] = min(nums[i]...nums[n-1])
        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]);
        }

        long minSum = Long.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, (long)leftMin + nums[j] + rightMin);
            }
        }

        return minSum == Long.MAX_VALUE ? -1 : (int)minSum;
    }
}
```
### Algorithm
*   If array length `n < 3`, return -1.
*   Create a `prefixMin` array of size `n`. `prefixMin[i]` will store the minimum value in `nums[0...i]`. Populate it by iterating from left to right.
*   Create a `suffixMin` array of size `n`. `suffixMin[i]` will store the minimum value in `nums[i...n-1]`. Populate it by iterating from right to left.
*   Initialize `minSum` to a very large value.
*   Iterate with index `j` from `1` to `n-2`.
*   For each `j`, the minimum element to its left is `prefixMin[j-1]` and to its right is `suffixMin[j+1]`.
*   Check if `prefixMin[j-1] < nums[j]` and `suffixMin[j+1] < nums[j]`.
*   If the condition is true, calculate the sum `prefixMin[j-1] + nums[j] + suffixMin[j+1]` and update `minSum`.
*   After the loop, if `minSum` is unchanged, 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

```