Minimum Sum of Mountain Triplets II solution and explanation
9 more videos on this problem
Leetcode Weekly contest 368 - Easy & Medium - Minimum Sum of Mountain Triplets II & IPrakhar Agrawal · 10:22 · 1K views
2909. Minimum Sum of Mountain Triplets II - LeetCode Python tutorialCode with Carter · 14:28 · 523 views
Leetcode Weekly Contest 368 || Problems A, B, C || 2908, 2909, 2910 || CodeaticCode-a-tic · 27:35 · 480 views
2908 Minimum Sum of Mountain Triplets I 2909 Minimum Sum of Mountain Triplets II Weekly Contest 368Ashish Kumar · 9:44 · 425 views
2909. Minimum Sum of Mountain Triplets II | LeetCode Weekly Contest-368 | Fully ExplainedAlgoArtist · 8:16 · 372 views
2909. Minimum Sum of Mountain Triplets II (Leetcode Medium)Programming Live with Larry · 6:28 · 229 views
100114 Minimum Sum of Mountain Triplets II || leetcode || contest368 || weekly contest || solutionSsquare · 1:11 · 187 views
Leetcode 2909. Minimum Sum of Mountain Triplets IIElite Code · 19:41 · 99 views
Minimum Sum Of Mountain Triplets IIOwen Wu · 8:04 · 23 views
Minimum Sum of Mountain Triplets Leetcode | Weekly Contest 368 | Solutions | Editorial | AbhinavAbhinav Awasthi · 8:02 · 1K views
The problem
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]andnums[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] <= 108
Approach overview
Problem Overview: You are given an integer array and must find a triplet (i, j, k) such that i < j < k, nums[i] < nums[j], and nums[k] < nums[j]. The element at index j acts as the mountain peak. Among all valid mountain triplets, return the minimum possible value of nums[i] + nums[j] + nums[k]. If no valid triplet exists, return -1. The challenge is efficiently identifying smaller elements on both sides of every potential peak.
Approach 1: Peak and Two-Pointer Strategy (O(n²) time, O(1) space)
Treat every index j as the potential mountain peak. For each peak, scan the left side to find the smallest value nums[i] where i < j and nums[i] < nums[j]. Then scan the right side to find the smallest value nums[k] where k > j and nums[k] < nums[j]. If both exist, compute the sum and track the minimum across all peaks. This approach relies only on direct iteration and works well for understanding the constraint structure of the problem. However, repeatedly scanning both sides for every peak leads to quadratic time complexity. You mainly use basic array traversal with pointer movement similar to manual two‑pointer exploration.
Approach 2: Optimized Precomputation Method (O(n) time, O(n) space)
The key observation: for every potential peak j, you only need the smallest valid value on the left and the smallest valid value on the right. Precompute a prefix minimum array where leftMin[j] stores the smallest element seen before index j. Similarly compute a suffix minimum array where rightMin[j] stores the smallest element to the right of j. Then iterate through the array once and treat each index as the peak. A valid mountain exists only if leftMin[j] < nums[j] and rightMin[j] < nums[j]. When both conditions hold, calculate leftMin[j] + nums[j] + rightMin[j] and update the global minimum.
This preprocessing removes repeated scanning. Each element is processed a constant number of times: once during prefix computation, once during suffix computation, and once during the peak evaluation pass. The result is linear time complexity with predictable memory usage, making it the most practical approach for large arrays.
Recommended for interviews: The optimized precomputation method is the expected solution. Interviewers want to see that you convert repeated searches into prefix/suffix preprocessing, a common pattern in array problems. Mentioning the naive scanning approach first shows you understand the problem structure, while implementing the O(n) optimization demonstrates strong algorithmic thinking.
Approach 1: Peak and Two-Pointer Strategy
This approach focuses on identifying the peak elements first and then applies a two-pointer strategy to find the minimum sum of a mountain triplet. The idea is to try each element as the peak (the middle element of a triplet) and find the smallest elements on either side under the given constraints.
def minMountainTripletSum(nums):
min_sum = float('inf')
for j in range(1, len(nums) - 1):
left_min = float('inf')
for i in range(j):
if nums[i] < nums[j] and nums[i] < left_min:
left_min = nums[i]
right_min = float('inf')
for k in range(j + 1, len(nums)):
if nums[k] < nums[j] and nums[k] < right_min:
right_min = nums[k]
if left_min != float('inf') and right_min != float('inf'):
current_sum = left_min + nums[j] + right_min
min_sum = min(min_sum, current_sum)
return -1 if min_sum == float('inf') else min_sum
nums = [8, 6, 1, 5, 3]
print(minMountainTripletSum(nums))import java.util.*;
public class Main {
public static int minMountainTripletSum(int[] nums) {
int minSum = Integer.MAX_VALUE;
for (int j = 1; j < nums.length - 1; j++) {
int left_min = Integer.MAX_VALUE;
for (int i = 0; i < j; i++) {
if (nums[i] < nums[j] && nums[i] < left_min) {
left_min = nums[i];
}
}
int right_min = Integer.MAX_VALUE;
for (int k = j + 1; k < nums.length; k++) {
if (nums[k] < nums[j] && nums[k] < right_min) {
right_min = nums[k];
}
}
if (left_min != Integer.MAX_VALUE && right_min != Integer.MAX_VALUE) {
int sum = left_min + nums[j] + right_min;
if (sum < minSum) {
minSum = sum;
}
}
}
return minSum == Integer.MAX_VALUE ? -1 : minSum;
}
public static void main(String[] args) {
int[] nums = {8, 6, 1, 5, 3};
System.out.println(minMountainTripletSum(nums));
}
}#include <vector>
#include <iostream>
#include <climits>
using namespace std;
int minMountainTripletSum(vector<int>& nums) {
int minSum = INT_MAX;
for (int j = 1; j < nums.size() - 1; j++) {
int left_min = INT_MAX;
for (int i = 0; i < j; i++) {
if (nums[i] < nums[j] && nums[i] < left_min) {
left_min = nums[i];
}
}
int right_min = INT_MAX;
for (int k = j + 1; k < nums.size(); k++) {
if (nums[k] < nums[j] && nums[k] < right_min) {
right_min = nums[k];
}
}
if (left_min != INT_MAX && right_min != INT_MAX) {
int sum = left_min + nums[j] + right_min;
if (sum < minSum) {
minSum = sum;
}
}
}
return minSum == INT_MAX ? -1 : minSum;
}
int main() {
vector<int> nums = {8, 6, 1, 5, 3};
cout << minMountainTripletSum(nums) << endl;
return 0;
}function minMountainTripletSum(nums) {
let minSum = Number.MAX_VALUE;
for (let j = 1; j < nums.length - 1; j++) {
let leftMin = Number.MAX_VALUE;
for (let i = 0; i < j; i++) {
if (nums[i] < nums[j] && nums[i] < leftMin) {
leftMin = nums[i];
}
}
let rightMin = Number.MAX_VALUE;
for (let k = j + 1; k < nums.length; k++) {
if (nums[k] < nums[j] && nums[k] < rightMin) {
rightMin = nums[k];
}
}
if (leftMin !== Number.MAX_VALUE && rightMin !== Number.MAX_VALUE) {
minSum = Math.min(minSum, leftMin + nums[j] + rightMin);
}
}
return minSum === Number.MAX_VALUE ? -1 : minSum;
}
const nums = [8, 6, 1, 5, 3];
console.log(minMountainTripletSum(nums));#include <stdio.h>
#include <limits.h>
int minMountainTripletSum(int* nums, int numsSize) {
int minSum = INT_MAX;
for (int j = 1; j < numsSize - 1; j++) {
int left_min = INT_MAX;
for (int i = 0; i < j; i++) {
if (nums[i] < nums[j] && nums[i] < left_min) {
left_min = nums[i];
}
}
int right_min = INT_MAX;
for (int k = j + 1; k < numsSize; k++) {
if (nums[k] < nums[j] && nums[k] < right_min) {
right_min = nums[k];
}
}
if (left_min != INT_MAX && right_min != INT_MAX) {
int sum = left_min + nums[j] + right_min;
if (sum < minSum) {
minSum = sum;
}
}
}
return minSum == INT_MAX ? -1 : minSum;
}
int main() {
int nums[] = {8, 6, 1, 5, 3};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", minMountainTripletSum(nums, numsSize));
return 0;
}using System;
public class Program {
public static int MinMountainTripletSum(int[] nums) {
int minSum = int.MaxValue;
for (int j = 1; j < nums.Length - 1; j++) {
int leftMin = int.MaxValue;
for (int i = 0; i < j; i++) {
if (nums[i] < nums[j] && nums[i] < leftMin) {
leftMin = nums[i];
}
}
int rightMin = int.MaxValue;
for (int k = j + 1; k < nums.Length; k++) {
if (nums[k] < nums[j] && nums[k] < rightMin) {
rightMin = nums[k];
}
}
if (leftMin != int.MaxValue && rightMin != int.MaxValue) {
int sum = leftMin + nums[j] + rightMin;
minSum = Math.Min(minSum, sum);
}
}
return minSum == int.MaxValue ? -1 : minSum;
}
public static void Main() {
int[] nums = {8, 6, 1, 5, 3};
Console.WriteLine(MinMountainTripletSum(nums));
}
}In the Python version, we utilize the same core strategy: choosing each point as a possible peak and determining the smallest qualifying elements for the triplet sum. This repeats for every middle index.
Time Complexity: O(n^2)
Space Complexity: O(1)
Approach 2: Optimized Precomputation Method
This method reduces the complexity by precomputing the smallest elements to the left and right for each potential peak. We make use of two auxiliary arrays to store these values, thereby reducing redundant computation within the nested loops.
def minMountainTripletSum(nums):
left_min = [float('inf')] * len(nums)
right_min = [float('inf')] * len(nums)
for i in range(1, len(nums)):
left_min[i] = min(left_min[i - 1], nums[i - 1])
for i in range(len(nums) - 2, -1, -1):
right_min[i] = min(right_min[i + 1], nums[i + 1])
min_sum = float('inf')
for j in range(1, len(nums) - 1):
if left_min[j] < nums[j] and nums[j] > right_min[j]:
min_sum = min(min_sum, left_min[j] + nums[j] + right_min[j])
return -1 if min_sum == float('inf') else min_sum
nums = [8, 6, 1, 5, 3]
print(minMountainTripletSum(nums))import java.util.*;
public class Main {
public static int minMountainTripletSum(int[] nums) {
int[] left_min = new int[nums.length];
int[] right_min = new int[nums.length];
Arrays.fill(left_min, Integer.MAX_VALUE);
Arrays.fill(right_min, Integer.MAX_VALUE);
for (int i = 1; i < nums.length; i++) {
left_min[i] = Math.min(left_min[i - 1], nums[i - 1]);
}
for (int i = nums.length - 2; i >= 0; i--) {
right_min[i] = Math.min(right_min[i + 1], nums[i + 1]);
}
int minSum = Integer.MAX_VALUE;
for (int j = 1; j < nums.length - 1; j++) {
if (left_min[j] < nums[j] && nums[j] > right_min[j]) {
minSum = Math.min(minSum, left_min[j] + nums[j] + right_min[j]);
}
}
return minSum == Integer.MAX_VALUE ? -1 : minSum;
}
public static void main(String[] args) {
int[] nums = {8, 6, 1, 5, 3};
System.out.println(minMountainTripletSum(nums));
}
}#include <vector>
#include <iostream>
#include <climits>
using namespace std;
int minMountainTripletSum(vector<int>& nums) {
vector<int> left_min(nums.size(), INT_MAX);
vector<int> right_min(nums.size(), INT_MAX);
for (int i = 1; i < nums.size(); i++) {
left_min[i] = min(left_min[i - 1], nums[i - 1]);
}
for (int i = nums.size() - 2; i >= 0; i--) {
right_min[i] = min(right_min[i + 1], nums[i + 1]);
}
int minSum = INT_MAX;
for (int j = 1; j < nums.size() - 1; j++) {
if (left_min[j] < nums[j] && nums[j] > right_min[j]) {
minSum = min(minSum, left_min[j] + nums[j] + right_min[j]);
}
}
return minSum == INT_MAX ? -1 : minSum;
}
int main() {
vector<int> nums = {8, 6, 1, 5, 3};
cout << minMountainTripletSum(nums) << endl;
return 0;
}function minMountainTripletSum(nums) {
let leftMin = new Array(nums.length).fill(Number.MAX_VALUE);
let rightMin = new Array(nums.length).fill(Number.MAX_VALUE);
for (let i = 1; i < nums.length; i++) {
leftMin[i] = Math.min(leftMin[i - 1], nums[i - 1]);
}
for (let i = nums.length - 2; i >= 0; i--) {
rightMin[i] = Math.min(rightMin[i + 1], nums[i + 1]);
}
let minSum = Number.MAX_VALUE;
for (let j = 1; j < nums.length - 1; j++) {
if (leftMin[j] < nums[j] && nums[j] > rightMin[j]) {
minSum = Math.min(minSum, leftMin[j] + nums[j] + rightMin[j]);
}
}
return minSum === Number.MAX_VALUE ? -1 : minSum;
}
const nums = [8, 6, 1, 5, 3];
console.log(minMountainTripletSum(nums));#include <stdio.h>
#include <limits.h>
int minMountainTripletSum(int* nums, int numsSize) {
int left_min[numsSize];
int right_min[numsSize];
left_min[0] = INT_MAX;
for (int i = 1; i < numsSize; i++) {
left_min[i] = nums[i - 1] < left_min[i - 1] ? nums[i - 1] : left_min[i - 1];
}
right_min[numsSize - 1] = INT_MAX;
for (int i = numsSize - 2; i >= 0; i--) {
right_min[i] = nums[i + 1] < right_min[i + 1] ? nums[i + 1] : right_min[i + 1];
}
int minSum = INT_MAX;
for (int j = 1; j < numsSize - 1; j++) {
if (left_min[j] < nums[j] && right_min[j] < nums[j]) {
int sum = left_min[j] + nums[j] + right_min[j];
if (sum < minSum) {
minSum = sum;
}
}
}
return minSum == INT_MAX ? -1 : minSum;
}
int main() {
int nums[] = {8, 6, 1, 5, 3};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", minMountainTripletSum(nums, numsSize));
return 0;
}using System;
public class Program {
public static int MinMountainTripletSum(int[] nums) {
int[] leftMin = new int[nums.Length];
int[] rightMin = new int[nums.Length];
for (int i = 0; i < leftMin.Length; i++) leftMin[i] = int.MaxValue;
for (int i = 0; i < rightMin.Length; i++) rightMin[i] = int.MaxValue;
for (int i = 1; i < nums.Length; i++) {
leftMin[i] = Math.Min(leftMin[i - 1], nums[i - 1]);
}
for (int i = nums.Length - 2; i >= 0; i--) {
rightMin[i] = Math.Min(rightMin[i + 1], nums[i + 1]);
}
int minSum = int.MaxValue;
for (int j = 1; j < nums.Length - 1; j++) {
if (leftMin[j] < nums[j] && nums[j] > rightMin[j]) {
minSum = Math.Min(minSum, leftMin[j] + nums[j] + rightMin[j]);
}
}
return minSum == int.MaxValue ? -1 : minSum;
}
public static void Main() {
int[] nums = {8, 6, 1, 5, 3};
Console.WriteLine(MinMountainTripletSum(nums));
}
}This Python solution improves efficiency by precomputing decreasing values spanning both sides of each entity, thus converting the overall complexity to linear scale.
Time Complexity: O(n)
Space Complexity: O(n)
Approach 3: Preprocessing + Enumeration
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.
function minimumSum(nums: number[]): number {
const n = nums.length;
const right: number[] = Array(n + 1).fill(Infinity);
for (let i = n - 1; ~i; --i) {
right[i] = Math.min(right[i + 1], nums[i]);
}
let [ans, left] = [Infinity, Infinity];
for (let i = 0; i < n; ++i) {
if (left < nums[i] && right[i + 1] < nums[i]) {
ans = Math.min(ans, left + nums[i] + right[i + 1]);
}
left = Math.min(left, nums[i]);
}
return ans === Infinity ? -1 : ans;
}func minimumSum(nums []int) int {
n := len(nums)
const inf = 1 << 30
right := make([]int, n+1)
right[n] = inf
for i := n - 1; i >= 0; i-- {
right[i] = min(right[i+1], nums[i])
}
ans, left := inf, inf
for i, x := range nums {
if left < x && right[i+1] < x {
ans = min(ans, left+x+right[i+1])
}
left = min(left, x)
}
if ans == inf {
return -1
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Peak and Two-Pointer Strategy | Time Complexity: O(n^2) |
| Optimized Precomputation Method | Time Complexity: O(n) |
| Preprocessing + Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Peak and Two-Pointer Strategy | O(n²) | O(1) | Useful for understanding the problem structure or when input size is small |
| Optimized Precomputation Method | O(n) | O(n) | Best choice for interviews and large arrays; avoids repeated scanning by using prefix and suffix minimums |
Frequently asked questions
Is Minimum Sum of Mountain Triplets II easy or hard?
Minimum Sum of Mountain Triplets II is generally considered a medium-level array problem. The brute-force idea is simple, but recognizing that prefix and suffix minimum preprocessing reduces the complexity to O(n) requires stronger algorithmic intuition.
Minimum Sum of Mountain Triplets II Python/Java solution
Python, Java, C++, C, C#, and JavaScript implementations typically follow the same pattern: compute prefix minimums, compute suffix minimums, then iterate through each index as a peak candidate. The logic remains identical across languages, with overall O(n) time complexity.
How to solve Minimum Sum of Mountain Triplets II in O(n)?
Precompute the smallest element to the left of every index and the smallest element to the right using prefix and suffix arrays. Then iterate through each index j as a peak and check if both sides contain values smaller than nums[j]. When they do, compute the sum and keep the minimum. Each element is processed a constant number of times, giving O(n) complexity.
What is the best approach for Minimum Sum of Mountain Triplets II?
The optimal approach uses prefix and suffix minimum precomputation. For each index j treated as the peak, track the smallest value to its left and right. If both are smaller than nums[j], compute the triplet sum. This method runs in O(n) time and is the solution most interviewers expect.
Is Minimum Sum of Mountain Triplets II asked at Google/Amazon/Meta?
Mountain or peak-based array problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants that require prefix or suffix preprocessing are common because they test optimization skills and pattern recognition.
What data structure is used in Minimum Sum of Mountain Triplets II?
The problem primarily uses arrays for prefix minimum and suffix minimum preprocessing. These arrays allow constant-time lookups for the smallest value on either side of a potential peak while iterating through the original array.
What is the time complexity of Minimum Sum of Mountain Triplets II?
The optimized solution runs in O(n) time by preprocessing prefix and suffix minimum arrays and scanning the array once more to evaluate peaks. A straightforward scanning approach that checks both sides for every index takes O(n²) time.