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] <= 50Problem Overview: You are given an integer array nums. A valid mountain triplet (i, j, k) must satisfy i < j < k and nums[i] < nums[j] and nums[k] < nums[j]. The goal is to find the minimum possible sum nums[i] + nums[j] + nums[k]. If no such triplet exists, return -1. The challenge is efficiently identifying a middle peak while ensuring smaller values exist on both sides.
Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)
The direct solution checks every possible triplet. Use three nested loops to iterate over indices i, j, and k such that i < j < k. For each combination, verify the mountain condition nums[i] < nums[j] and nums[k] < nums[j]. If valid, compute the sum and track the minimum. This approach works because it exhaustively explores the search space, but the O(n^3) time complexity becomes impractical as the array grows. Still useful as a baseline or when explaining the problem during interviews to demonstrate understanding before optimizing. The algorithm operates directly on the array with no additional data structures.
Approach 2: Optimized Two-Pass with Prefix and Suffix Minimums (O(n) time, O(n) space)
The key observation: for a fixed middle index j, you only need the smallest value on the left that is less than nums[j] and the smallest value on the right that is also less than nums[j]. Instead of searching every time, precompute this information.
First pass: build a prefix array where leftMin[j] stores the minimum value seen before index j. Second pass from right to left: maintain a running suffix minimum representing the smallest value to the right. For each index j, check whether both sides contain values smaller than nums[j]. If they do, compute the candidate sum leftMin[j] + nums[j] + rightMin and update the global minimum.
This turns the triple search into two linear scans. Each index is processed a constant number of times, giving O(n) time complexity with O(n) auxiliary space for prefix tracking. The technique relies on maintaining running minimums, a common pattern in array problems and prefix-style preprocessing similar to prefix-based techniques.
Recommended for interviews: Interviewers expect the two-pass optimized solution. Starting with brute force shows you understand the mountain constraint and index ordering. Transitioning to the prefix/suffix minimum idea demonstrates pattern recognition and the ability to reduce O(n^3) enumeration to an O(n) scan, which is the key skill being evaluated.
This approach involves selecting each element as a potential peak and then searching for left and right valleys. This method is straightforward but non-optimal with a time complexity of O(n^3).
The C solution implements a nested loop to consider each potential peak element. It then iterates over all possible left and right elements to determine valid valleys forming a mountain triplet. If valid, calculates the triplet sum and updates the minimum sum found.
Time Complexity: O(n^3)
Space Complexity: O(1)
This approach involves two passes to precompute possible candidates for left and right valleys for each element, and then determining the minimum triplet sum. This method optimizes the previous approach by reducing redundancy and yields an O(n^2) time complexity.
This optimized C approach first precomputes possible minimum valley elements to the left and right of each element, iterating over them efficiently to evaluate and compute mountain triplet sums.
Time Complexity: O(n^2)
Space Complexity: O(n)
We can preprocess the minimum value on the right side of each position and record it in the array right[i], where right[i] represents the minimum value in nums[i+1..n-1].
Next, we enumerate the middle element nums[i] of the mountain triplet from left to right, and use a variable left to represent the minimum value in ums[0..i-1], and a variable ans to represent the current minimum element sum found. For each i, we need to find the element nums[i] that satisfies left < nums[i] and right[i+1] < nums[i], and update ans.
Finally, if ans is still the initial value, it means that there is no mountain triplet, and we return -1.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3) |
| Optimized Two-Pass Approach | Time Complexity: O(n^2) |
| Preprocessing + Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^3) | O(1) | Small arrays or when explaining the baseline logic in interviews |
| Two-Pass Prefix & Suffix Minimum | O(n) | O(n) | General case; optimal approach expected in coding interviews |
LeetCode#2908 Minimum Sum of Mountain Triplets I - Python • CodeJulian • 2,024 views views
Watch 9 more video solutions →Practice Minimum Sum of Mountain Triplets I with our built-in code editor and test cases.
Practice on FleetCode