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 <= 50
  • 1 <= nums[i] <= 50

Solution

Method 1 – Brute Force Enumeration

Intuition

Since the array is small (n ≤ 50), we can check all possible triplets (i, j, k) and find the minimum sum for those that form a mountain.

Approach

  1. For each j from 1 to n-2, try all i < j and k > j.
  2. If nums[i] < nums[j] and nums[k] < nums[j], update the minimum sum.
  3. 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

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

func minimumSum(nums []int) int {
    n := len(nums)
    ans := 1<<31-1
    for j := 1; j < n-1; j++ {
        for i := 0; i < j; i++ {
            if nums[i] < nums[j] {
                for k := j+1; k < n; k++ {
                    if nums[k] < nums[j] {
                        sum := nums[i]+nums[j]+nums[k]
                        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

class Solution {
    public int minimumSum(int[] nums) {
        int n = nums.length, ans = Integer.MAX_VALUE;
        for (int j = 1; j < n-1; j++) {
            for (int i = 0; i < j; i++) {
                if (nums[i] < nums[j]) {
                    for (int k = j+1; k < n; k++) {
                        if (nums[k] < nums[j]) {
                            ans = Math.min(ans, nums[i]+nums[j]+nums[k]);
                        }
                    }
                }
            }
        }
        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

class Solution {
    fun minimumSum(nums: IntArray): Int {
        val n = nums.size
        var ans = Int.MAX_VALUE
        for (j in 1 until n-1) {
            for (i in 0 until j) {
                if (nums[i] < nums[j]) {
                    for (k in j+1 until n) {
                        if (nums[k] < nums[j]) {
                            ans = minOf(ans, nums[i]+nums[j]+nums[k])
                        }
                    }
                }
            }
        }
        return if (ans == Int.MAX_VALUE) -1 else ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def minimumSum(self, nums: list[int]) -> int:
        n = len(nums)
        ans = float('inf')
        for j in range(1, n-1):
            for i in range(j):
                if nums[i] < nums[j]:
                    for k in range(j+1, n):
                        if nums[k] < nums[j]:
                            ans = min(ans, nums[i]+nums[j]+nums[k])
        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

impl Solution {
    pub fn minimum_sum(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut ans = i32::MAX;
        for j in 1..n-1 {
            for i in 0..j {
                if nums[i] < nums[j] {
                    for k in j+1..n {
                        if nums[k] < nums[j] {
                            ans = ans.min(nums[i]+nums[j]+nums[k]);
                        }
                    }
                }
            }
        }
        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

class Solution {
    minimumSum(nums: number[]): number {
        const n = nums.length;
        let ans = Infinity;
        for (let j = 1; j < n-1; j++) {
            for (let i = 0; i < j; i++) {
                if (nums[i] < nums[j]) {
                    for (let k = j+1; k < n; k++) {
                        if (nums[k] < nums[j]) {
                            ans = Math.min(ans, nums[i]+nums[j]+nums[k]);
                        }
                    }
                }
            }
        }
        return ans === Infinity ? -1 : ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^3) — Three nested loops, but n ≤ 50.
  • 🧺 Space complexity: O(1) — Only counters used.