You are given a 0-indexed array nums of integers.
A triplet of indices (i, j, k) is a mountain if:
i < j < knums[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 <= 501 <= nums[i] <= 50In #2908 Minimum Sum of Mountain Triplets I, we need to find indices i < j < k such that nums[i] < nums[j] and nums[k] < nums[j]. Among all such "mountain" triplets, the goal is to return the minimum possible sum of nums[i] + nums[j] + nums[k]. If no valid triplet exists, return -1.
A key observation is that for each middle index j, we only need the smallest valid element on the left and the smallest valid element on the right that are both smaller than nums[j]. This can be optimized using two helper arrays: a prefix minimum to track the smallest value to the left of each index, and a suffix minimum to track the smallest value to the right.
While iterating through the array as the potential peak j, check whether both sides contain elements smaller than nums[j]. If so, compute the candidate sum and update the minimum. This approach avoids checking all triplets and reduces the complexity significantly.
The optimized solution runs in O(n) time with O(n) additional space for prefix and suffix tracking.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force (check all triplets) | O(n^3) | O(1) |
| Prefix & Suffix Minimum Optimization | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Bruteforce over all possible triplets.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
They allow quick lookup of the smallest element before and after each index. This avoids checking every possible triplet and reduces the time complexity from cubic to linear.
Yes, similar array optimization and prefix/suffix technique problems are common in coding interviews. They test your ability to reduce brute-force solutions using precomputation and efficient scanning.
Simple arrays are sufficient for this problem. Prefix and suffix arrays help efficiently track the smallest values to the left and right of each index while scanning the array once.
The optimal approach uses prefix and suffix minimum arrays. For each index treated as the middle element, check the smallest value on the left and right that is smaller than it, then compute the minimum possible sum.