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 theminimum possible sum of a mountain triplet of nums. If no such triplet exists, return -1.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4
5
6

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

1
2
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 <= 10^5
  • 1 <= nums[i] <= 10^8

Solution

Method 1 – Prefix and Suffix Min Arrays

Intuition

For each possible middle index j, find the smallest nums[i] to the left of j (where nums[i] < nums[j]) and the smallest nums[k] to the right of j (where nums[k] < nums[j]). The minimum sum among all valid triplets is the answer.

Approach

  1. For each index, build prefix min array for left candidates (nums[i] < nums[j]).
  2. Build suffix min array for right candidates (nums[k] < nums[j]).
  3. For each j, if both left and right candidates exist, update the answer with their sum.
  4. Return the minimum sum found, or -1 if no triplet exists.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int minimumSum(vector<int>& nums) {
        int n = nums.size(), ans = INT_MAX;
        vector<int> left(n, INT_MAX), right(n, INT_MAX);
        int minl = INT_MAX;
        for (int i = 0; i < n; ++i) {
            left[i] = minl;
            if (nums[i] < minl) minl = nums[i];
        }
        int minr = INT_MAX;
        for (int i = n-1; i >= 0; --i) {
            right[i] = minr;
            if (nums[i] < minr) minr = nums[i];
        }
        for (int j = 1; j < n-1; ++j) {
            if (left[j] < nums[j] && right[j] < nums[j])
                ans = min(ans, left[j] + nums[j] + right[j]);
        }
        return ans == INT_MAX ? -1 : ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func minimumSum(nums []int) int {
    n := len(nums)
    left := make([]int, n)
    right := make([]int, n)
    minl := 1<<31-1
    for i := 0; i < n; i++ {
        left[i] = minl
        if nums[i] < minl { minl = nums[i] }
    }
    minr := 1<<31-1
    for i := n-1; i >= 0; i-- {
        right[i] = minr
        if nums[i] < minr { minr = nums[i] }
    }
    ans := 1<<31-1
    for j := 1; j < n-1; j++ {
        if left[j] < nums[j] && right[j] < nums[j] {
            sum := left[j] + nums[j] + right[j]
            if sum < ans { ans = sum }
        }
    }
    if ans == 1<<31-1 { return -1 }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int minimumSum(int[] nums) {
        int n = nums.length, ans = Integer.MAX_VALUE;
        int[] left = new int[n], right = new int[n];
        int minl = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            left[i] = minl;
            if (nums[i] < minl) minl = nums[i];
        }
        int minr = Integer.MAX_VALUE;
        for (int i = n-1; i >= 0; i--) {
            right[i] = minr;
            if (nums[i] < minr) minr = nums[i];
        }
        for (int j = 1; j < n-1; j++) {
            if (left[j] < nums[j] && right[j] < nums[j])
                ans = Math.min(ans, left[j] + nums[j] + right[j]);
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    fun minimumSum(nums: IntArray): Int {
        val n = nums.size
        val left = IntArray(n)
        val right = IntArray(n)
        var minl = Int.MAX_VALUE
        for (i in 0 until n) {
            left[i] = minl
            if (nums[i] < minl) minl = nums[i]
        }
        var minr = Int.MAX_VALUE
        for (i in n-1 downTo 0) {
            right[i] = minr
            if (nums[i] < minr) minr = nums[i]
        }
        var ans = Int.MAX_VALUE
        for (j in 1 until n-1) {
            if (left[j] < nums[j] && right[j] < nums[j])
                ans = minOf(ans, left[j] + nums[j] + right[j])
        }
        return if (ans == Int.MAX_VALUE) -1 else ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def minimumSum(self, nums: list[int]) -> int:
        n = len(nums)
        left = [float('inf')] * n
        right = [float('inf')] * n
        minl = float('inf')
        for i in range(n):
            left[i] = minl
            if nums[i] < minl: minl = nums[i]
        minr = float('inf')
        for i in range(n-1, -1, -1):
            right[i] = minr
            if nums[i] < minr: minr = nums[i]
        ans = float('inf')
        for j in range(1, n-1):
            if left[j] < nums[j] and right[j] < nums[j]:
                ans = min(ans, left[j] + nums[j] + right[j])
        return -1 if ans == float('inf') else ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

impl Solution {
    pub fn minimum_sum(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut left = vec![i32::MAX; n];
        let mut right = vec![i32::MAX; n];
        let mut minl = i32::MAX;
        for i in 0..n {
            left[i] = minl;
            if nums[i] < minl { minl = nums[i]; }
        }
        let mut minr = i32::MAX;
        for i in (0..n).rev() {
            right[i] = minr;
            if nums[i] < minr { minr = nums[i]; }
        }
        let mut ans = i32::MAX;
        for j in 1..n-1 {
            if left[j] < nums[j] && right[j] < nums[j] {
                ans = ans.min(left[j] + nums[j] + right[j]);
            }
        }
        if ans == i32::MAX { -1 } else { ans }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    minimumSum(nums: number[]): number {
        const n = nums.length;
        const left = Array(n).fill(Infinity);
        const right = Array(n).fill(Infinity);
        let minl = Infinity;
        for (let i = 0; i < n; i++) {
            left[i] = minl;
            if (nums[i] < minl) minl = nums[i];
        }
        let minr = Infinity;
        for (let i = n-1; i >= 0; i--) {
            right[i] = minr;
            if (nums[i] < minr) minr = nums[i];
        }
        let ans = Infinity;
        for (let j = 1; j < n-1; j++) {
            if (left[j] < nums[j] && right[j] < nums[j])
                ans = Math.min(ans, left[j] + nums[j] + right[j]);
        }
        return ans === Infinity ? -1 : ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — One pass for prefix, one for suffix, one for answer.
  • 🧺 Space complexity: O(n) — For left and right arrays.