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 <= 1051 <= nums[i] <= 108In #2909 Minimum Sum of Mountain Triplets II, the goal is to find three indices i < j < k such that nums[i] < nums[j] and nums[k] < nums[j], forming a mountain with nums[j] as the peak. Among all valid triplets, we must return the minimum possible sum.
A key observation is that for each position j, we only need the smallest value on the left and the smallest value on the right. Precompute a suffix array where rightMin[i] stores the minimum element from index i to the end. While iterating through the array, maintain a running prefix minimum to represent the smallest value on the left.
For each potential peak j, check whether both sides contain values strictly smaller than nums[j]. If so, compute the candidate sum leftMin + nums[j] + rightMin and track the minimum across all peaks. This efficient scanning approach avoids brute-force triplet enumeration and keeps the solution linear.
Time Complexity: O(n) with preprocessing. Space Complexity: O(n) for the suffix minimum array.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Prefix Minimum + Suffix Minimum Scan | O(n) | O(n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
If you fix index <code>j</code>, <code>i</code> will be the smallest integer to the left of <code>j</code>, and <code>k</code> the largest integer to the right of <code>j</code>.
To find <code>i</code> and <code>k</code>, preprocess the prefix minimum array <code>prefix_min[i] = min(nums[0], nums[1], ..., nums[i])</code>, and the suffix minimum array <code>suffix_min[i] = min(nums[i], nums[i + 1], ..., nums[i - 1])</code>.
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 access to the smallest values on both sides of a potential peak. Instead of checking all pairs on the left and right, we can determine valid mountain triplets in constant time per index.
Problems involving array scanning, prefix/suffix preprocessing, and pattern detection are common in FAANG-style interviews. This question tests optimization and observation skills often expected in technical coding rounds.
Arrays are sufficient for this problem. A suffix minimum array helps track the smallest value to the right, while a running prefix minimum tracks the smallest value to the left during iteration.
The optimal approach uses prefix and suffix minimum values. For each index as a potential peak, check the smallest value on the left and right that are smaller than the peak, then compute the triplet sum. This reduces the problem to a linear scan with preprocessing.