Minimum Sum of Mountain Triplets I — Problem & Solution
Minimum Sum of Mountain Triplets I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Minimum Sum of Mountain Triplets I is an easy coding problem on arrays and prefix sum, asked in Amazon, Google and Mindtree interviews.
- Difficulty: Easy
- Topics: Arrays, Prefix Sum
- Asked at: Amazon, Google, Mindtree
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Indices i < j < k form a mountain when nums[i] < nums[j] and nums[k] < nums[j].
Return the minimum possible value of nums[i] + nums[j] + nums[k] over all mountains, or -1 if there is none.
Example 1
Input: nums = [8,6,1,5,3]
Output: 9
Explanation: Indices 2, 3 and 4: `1 + 5 + 3`.
Example 2
Input: nums = [5,4,8,7,10,2]
Output: 13
Explanation: Indices 1, 3 and 5: `4 + 7 + 2`.
Example 3
Input: nums = [6,5,4,3,4,5]
Output: -1
Explanation: No index has a smaller value on both sides.
Constraints
3 <= nums.length <= 501 <= nums[i] <= 50
Hints for Minimum Sum of Mountain Triplets I
Hint 1
Fix the peak
jand the other two choices become independent.Hint 2
The best
iis the smallest value to the left, and the bestkthe smallest to the right.Hint 3
Precompute prefix and suffix minima in one pass each.
How to solve Minimum Sum of Mountain Triplets I
Treat each index as the peak. The cheapest mountain through it uses the smallest value on its left and the smallest on its right, so prefix and suffix minima answer every peak in O(1).
Approach
- Build
pre[i]= the minimum ofnums[0 … i]andsuf[i]= the minimum ofnums[i … n-1]. - For each
jfrom 1 ton - 2, checkpre[j-1] < nums[j]andsuf[j+1] < nums[j]. - Track the smallest total; return
-1if no peak qualifies.
Why it works
Fixing the peak decouples the two sides — the choice of i never constrains k — which is what turns an O(n³) scan over triples into two linear passes. Both inequalities are strict, so a flat plateau never forms a mountain.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Both comparisons are strict; equal neighbours do not make a peak.
- The first and last indices can never be the peak.
- Return
-1, not 0, when no mountain exists.
Reference solution
Python
from typing import List
def minimumSum(nums: List[int]) -> int:
n = len(nums)
pre = [0] * n
suf = [0] * n
pre[0] = nums[0]
for i in range(1, n):
pre[i] = min(pre[i - 1], nums[i])
suf[n - 1] = nums[n - 1]
for i in range(n - 2, -1, -1):
suf[i] = min(suf[i + 1], nums[i])
best = -1
for j in range(1, n - 1):
if pre[j - 1] < nums[j] and suf[j + 1] < nums[j]:
s = pre[j - 1] + nums[j] + suf[j + 1]
if best < 0 or s < best:
best = s
return bestJava
public static int minimumSum(int[] nums) {
int n = nums.length;
if (n < 3) return -1;
int[] pre = new int[n];
int[] suf = new int[n];
pre[0] = nums[0];
for (int i = 1; i < n; i++) pre[i] = Math.min(pre[i - 1], nums[i]);
suf[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; i--) suf[i] = Math.min(suf[i + 1], nums[i]);
int best = -1;
for (int j = 1; j + 1 < n; j++) {
if (pre[j - 1] < nums[j] && suf[j + 1] < nums[j]) {
int s = pre[j - 1] + nums[j] + suf[j + 1];
if (best < 0 || s < best) best = s;
}
}
return best;
}C++
int minimumSum(vector<int>& nums) {
int n = (int) nums.size();
if (n < 3) return -1;
vector<int> pre(n), suf(n);
pre[0] = nums[0];
for (int i = 1; i < n; i++) pre[i] = min(pre[i - 1], nums[i]);
suf[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; i--) suf[i] = min(suf[i + 1], nums[i]);
int best = -1;
for (int j = 1; j + 1 < n; j++) {
if (pre[j - 1] < nums[j] && suf[j + 1] < nums[j]) {
int s = pre[j - 1] + nums[j] + suf[j + 1];
if (best < 0 || s < best) best = s;
}
}
return best;
}JavaScript
var minimumSum = function(nums) {
var n = nums.length, i;
if (n < 3) return -1;
var pre = [], suf = [];
for (i = 0; i < n; i++) { pre.push(0); suf.push(0); }
pre[0] = nums[0];
for (i = 1; i < n; i++) pre[i] = Math.min(pre[i - 1], nums[i]);
suf[n - 1] = nums[n - 1];
for (i = n - 2; i >= 0; i--) suf[i] = Math.min(suf[i + 1], nums[i]);
var best = -1;
for (var j = 1; j + 1 < n; j++) {
if (pre[j - 1] < nums[j] && suf[j + 1] < nums[j]) {
var s = pre[j - 1] + nums[j] + suf[j + 1];
if (best < 0 || s < best) best = s;
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Prefix Sum