Minimum Sum of Mountain Triplets I 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
100106 Minimum Sum of Mountain Triplets I || leetcode || contest368 || weekly contest || solutionSsquare · 0:47 · 1K views
2908. Minimum Sum of Mountain Triplets I - LeetCode Python tutorialCode with Carter · 11:07 · 582 views
2908 Minimum Sum of Mountain Triplets I 2909 Minimum Sum of Mountain Triplets II Weekly Contest 368Ashish Kumar · 9:44 · 425 views
2908. Minimum Sum of Mountain Triplets I (Leetcode Easy)Programming Live with Larry · 5:15 · 204 views
Minimum Sum of Mountain Triplets I on leetcode #leetcodeManasa Duggempudi Academy · 7:16 · 115 views
Leetcode 2908 - Minimum Sum of Mountain Triplets ILuc Taylor · 4:51 · 104 views
Leetcode 2908 Minimum Sum of Mountain Triplets IAlgorithmicIQ · 18:07 · 48 views
#LeetCode 2908 | Minimum Sum of Mountain Triplets I #JavaSleepy Cracker · 6:04 · 38 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 <= 501 <= nums[i] <= 50
Approach overview
Problem 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.
Approach 1: Brute Force Approach
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).
def minMountainSum(nums):
min_sum = float('inf')
n = len(nums)
for j in range(1, n - 1):
min_left = float('inf')
min_right = float('inf')
for i in range(0, j):
if nums[i] < nums[j]:
min_left = min(min_left, nums[i])
for k in range(j + 1, n):
if nums[k] < nums[j]:
min_right = min(min_right, nums[k])
if min_left != float('inf') and min_right != float('inf'):
triplet_sum = min_left + nums[j] + min_right
min_sum = min(min_sum, triplet_sum)
return -1 if min_sum == float('inf') else min_sum
nums = [5, 4, 8, 7, 10, 2]
print(minMountainSum(nums))import java.util.*;
public class MinimumMountainSum {
public int minMountainSum(int[] nums) {
int minSum = Integer.MAX_VALUE;
int n = nums.length;
for (int j = 1; j < n - 1; j++) {
int minLeft = Integer.MAX_VALUE, minRight = Integer.MAX_VALUE;
for (int i = 0; i < j; i++) {
if (nums[i] < nums[j]) {
minLeft = Math.min(minLeft, nums[i]);
}
}
for (int k = j + 1; k < n; k++) {
if (nums[k] < nums[j]) {
minRight = Math.min(minRight, nums[k]);
}
}
if (minLeft != Integer.MAX_VALUE && minRight != Integer.MAX_VALUE) {
int sum = minLeft + nums[j] + minRight;
minSum = Math.min(minSum, sum);
}
}
return minSum == Integer.MAX_VALUE ? -1 : minSum;
}
public static void main(String[] args) {
MinimumMountainSum mms = new MinimumMountainSum();
int[] nums = {5, 4, 8, 7, 10, 2};
System.out.println(mms.minMountainSum(nums));
}
}#include <iostream>
#include <vector>
#include <climits>
int minMountainSum(const std::vector<int>& nums) {
int minSum = INT_MAX;
int n = nums.size();
for (int j = 1; j < n - 1; j++) {
int minLeft = INT_MAX, minRight = INT_MAX;
for (int i = 0; i < j; i++) {
if (nums[i] < nums[j]) {
minLeft = std::min(minLeft, nums[i]);
}
}
for (int k = j + 1; k < n; k++) {
if (nums[k] < nums[j]) {
minRight = std::min(minRight, nums[k]);
}
}
if (minLeft != INT_MAX && minRight != INT_MAX) {
int sum = minLeft + nums[j] + minRight;
minSum = std::min(minSum, sum);
}
}
return minSum == INT_MAX ? -1 : minSum;
}
int main() {
std::vector<int> nums = {5, 4, 8, 7, 10, 2};
int result = minMountainSum(nums);
std::cout << result << std::endl;
return 0;
}function minMountainSum(nums) {
let minSum = Number.MAX_SAFE_INTEGER;
let n = nums.length;
for (let j = 1; j < n - 1; j++) {
let minLeft = Number.MAX_SAFE_INTEGER;
let minRight = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < j; i++) {
if (nums[i] < nums[j]) {
minLeft = Math.min(minLeft, nums[i]);
}
}
for (let k = j + 1; k < n; k++) {
if (nums[k] < nums[j]) {
minRight = Math.min(minRight, nums[k]);
}
}
if (minLeft !== Number.MAX_SAFE_INTEGER && minRight !== Number.MAX_SAFE_INTEGER) {
let sum = minLeft + nums[j] + minRight;
minSum = Math.min(minSum, sum);
}
}
return minSum === Number.MAX_SAFE_INTEGER ? -1 : minSum;
}
let nums = [5, 4, 8, 7, 10, 2];
console.log(minMountainSum(nums));#include <stdio.h>
#include <limits.h>
int minMountainSum(int* nums, int numsSize) {
int minSum = INT_MAX;
for (int j = 1; j < numsSize - 1; j++) {
int minLeft = INT_MAX, minRight = INT_MAX;
for (int i = 0; i < j; i++) {
if (nums[i] < nums[j]) {
minLeft = minLeft < nums[i] ? minLeft : nums[i];
}
}
for (int k = j + 1; k < numsSize; k++) {
if (nums[k] < nums[j]) {
minRight = minRight < nums[k] ? minRight : nums[k];
}
}
if (minLeft != INT_MAX && minRight != INT_MAX) {
int sum = minLeft + nums[j] + minRight;
minSum = minSum < sum ? minSum : sum;
}
}
return minSum == INT_MAX ? -1 : minSum;
}
int main() {
int nums[] = {5, 4, 8, 7, 10, 2};
int result = minMountainSum(nums, 6);
printf("%d\n", result);
return 0;
}using System;
public class MountainTriplet {
public int MinMountainSum(int[] nums) {
int minSum = int.MaxValue;
int n = nums.Length;
for (int j = 1; j < n - 1; j++) {
int minLeft = int.MaxValue, minRight = int.MaxValue;
for (int i = 0; i < j; i++) {
if (nums[i] < nums[j]) {
minLeft = Math.Min(minLeft, nums[i]);
}
}
for (int k = j + 1; k < n; k++) {
if (nums[k] < nums[j]) {
minRight = Math.Min(minRight, nums[k]);
}
}
if (minLeft != int.MaxValue && minRight != int.MaxValue) {
int sum = minLeft + nums[j] + minRight;
minSum = Math.Min(minSum, sum);
}
}
return minSum == int.MaxValue ? -1 : minSum;
}
public static void Main(string[] args) {
MountainTriplet mt = new MountainTriplet();
int[] nums = {5, 4, 8, 7, 10, 2};
Console.WriteLine(mt.MinMountainSum(nums));
}
}The Python solution leverages list processing and nested loops to evaluate all possible mountain triplets, checking validity and computing the minimum sum.
Time Complexity: O(n^3)
Space Complexity: O(1)
Approach 2: Optimized Two-Pass Approach
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.
def minMountainSum(nums):
n = len(nums)
left_min = [float('inf')] * n
right_min = [float('inf')] * n
for j in range(1, n):
for i in range(0, j):
if nums[i] < nums[j]:
left_min[j] = min(left_min[j], nums[i])
for j in range(n-2, -1, -1):
for k in range(j+1, n):
if nums[k] < nums[j]:
right_min[j] = min(right_min[j], nums[k])
min_sum = float('inf')
for j in range(1, n-1):
if left_min[j] != float('inf') and right_min[j] != float('inf'):
triplet_sum = left_min[j] + nums[j] + right_min[j]
min_sum = min(min_sum, triplet_sum)
return -1 if min_sum == float('inf') else min_sum
nums = [5, 4, 8, 7, 10, 2]
print(minMountainSum(nums))import java.util.*;
public class MinimumMountainSum {
public int minMountainSum(int[] nums) {
int n = nums.length;
int[] leftMin = new int[n];
int[] rightMin = new int[n];
Arrays.fill(leftMin, Integer.MAX_VALUE);
Arrays.fill(rightMin, Integer.MAX_VALUE);
for (int j = 1; j < n; j++) {
for (int i = 0; i < j; i++) {
if (nums[i] < nums[j]) {
leftMin[j] = Math.min(leftMin[j], nums[i]);
}
}
}
for (int j = n - 2; j >= 0; j--) {
for (int k = j + 1; k < n; k++) {
if (nums[k] < nums[j]) {
rightMin[j] = Math.min(rightMin[j], nums[k]);
}
}
}
int minSum = Integer.MAX_VALUE;
for (int j = 1; j < n - 1; j++) {
if (leftMin[j] != Integer.MAX_VALUE && rightMin[j] != Integer.MAX_VALUE) {
int sum = leftMin[j] + nums[j] + rightMin[j];
minSum = Math.min(minSum, sum);
}
}
return minSum == Integer.MAX_VALUE ? -1 : minSum;
}
public static void main(String[] args) {
MinimumMountainSum mms = new MinimumMountainSum();
int[] nums = {5, 4, 8, 7, 10, 2};
System.out.println(mms.minMountainSum(nums));
}
}#include <iostream>
#include <vector>
#include <climits>
int minMountainSum(const std::vector<int>& nums) {
std::vector<int> leftMin(nums.size(), INT_MAX);
std::vector<int> rightMin(nums.size(), INT_MAX);
int n = nums.size();
for (int j = 1; j < n; j++) {
for (int i = 0; i < j; i++) {
if (nums[i] < nums[j]) {
leftMin[j] = std::min(leftMin[j], nums[i]);
}
}
}
for (int j = n - 2; j >= 0; j--) {
for (int k = j + 1; k < n; k++) {
if (nums[k] < nums[j]) {
rightMin[j] = std::min(rightMin[j], nums[k]);
}
}
}
int minSum = INT_MAX;
for (int j = 1; j < n - 1; j++) {
if (leftMin[j] != INT_MAX && rightMin[j] != INT_MAX) {
int sum = leftMin[j] + nums[j] + rightMin[j];
minSum = std::min(minSum, sum);
}
}
return minSum == INT_MAX ? -1 : minSum;
}
int main() {
std::vector<int> nums = {5, 4, 8, 7, 10, 2};
int result = minMountainSum(nums);
std::cout << result << std::endl;
return 0;
}function minMountainSum(nums) {
let n = nums.length;
let leftMin = new Array(n).fill(Number.MAX_SAFE_INTEGER);
let rightMin = new Array(n).fill(Number.MAX_SAFE_INTEGER);
for (let j = 1; j < n; j++) {
for (let i = 0; i < j; i++) {
if (nums[i] < nums[j]) {
leftMin[j] = Math.min(leftMin[j], nums[i]);
}
}
}
for (let j = n - 2; j >= 0; j--) {
for (let k = j + 1; k < n; k++) {
if (nums[k] < nums[j]) {
rightMin[j] = Math.min(rightMin[j], nums[k]);
}
}
}
let minSum = Number.MAX_SAFE_INTEGER;
for (let j = 1; j < n - 1; j++) {
if (leftMin[j] !== Number.MAX_SAFE_INTEGER && rightMin[j] !== Number.MAX_SAFE_INTEGER) {
let sum = leftMin[j] + nums[j] + rightMin[j];
minSum = Math.min(minSum, sum);
}
}
return minSum === Number.MAX_SAFE_INTEGER ? -1 : minSum;
}
let nums = [5, 4, 8, 7, 10, 2];
console.log(minMountainSum(nums));#include <stdio.h>
#include <limits.h>
int minMountainSum(int* nums, int numsSize) {
int leftMin[numsSize];
int rightMin[numsSize];
for (int i = 0; i < numsSize; i++) {
leftMin[i] = INT_MAX;
rightMin[i] = INT_MAX;
}
for (int j = 1; j < numsSize; j++) {
for (int i = 0; i < j; i++) {
if (nums[i] < nums[j]) {
leftMin[j] = leftMin[j] < nums[i] ? leftMin[j] : nums[i];
}
}
}
for (int j = numsSize - 2; j >= 0; j--) {
for (int k = j + 1; k < numsSize; k++) {
if (nums[k] < nums[j]) {
rightMin[j] = rightMin[j] < nums[k] ? rightMin[j] : nums[k];
}
}
}
int minSum = INT_MAX;
for (int j = 1; j < numsSize - 1; j++) {
if (leftMin[j] != INT_MAX && rightMin[j] != INT_MAX) {
int sum = leftMin[j] + nums[j] + rightMin[j];
minSum = minSum < sum ? minSum : sum;
}
}
return minSum == INT_MAX ? -1 : minSum;
}
int main() {
int nums[] = {5, 4, 8, 7, 10, 2};
int result = minMountainSum(nums, 6);
printf("%d\n", result);
return 0;
}using System;
public class MountainTriplet {
public int MinMountainSum(int[] nums) {
int n = nums.Length;
int[] leftMin = new int[n];
int[] rightMin = new int[n];
for (int i = 0; i < n; i++) {
leftMin[i] = int.MaxValue;
rightMin[i] = int.MaxValue;
}
for (int j = 1; j < n; j++) {
for (int i = 0; i < j; i++) {
if (nums[i] < nums[j]) {
leftMin[j] = Math.Min(leftMin[j], nums[i]);
}
}
}
for (int j = n - 2; j >= 0; j--) {
for (int k = j + 1; k < n; k++) {
if (nums[k] < nums[j]) {
rightMin[j] = Math.Min(rightMin[j], nums[k]);
}
}
}
int minSum = int.MaxValue;
for (int j = 1; j < n - 1; j++) {
if (leftMin[j] != int.MaxValue && rightMin[j] != int.MaxValue) {
int sum = leftMin[j] + nums[j] + rightMin[j];
minSum = Math.Min(minSum, sum);
}
}
return minSum == int.MaxValue ? -1 : minSum;
}
public static void Main(string[] args) {
MountainTriplet mt = new MountainTriplet();
int[] nums = {5, 4, 8, 7, 10, 2};
Console.WriteLine(mt.MinMountainSum(nums));
}
}Python optimizes on buffer arrays to keep track of viable candidates for valleys to each side of possible peaks across the array.
Time Complexity: O(n^2)
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 |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3) |
| Optimized Two-Pass Approach | Time Complexity: O(n^2) |
| Preprocessing + Enumeration | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Minimum Sum of Mountain Triplets I easy or hard?
Minimum Sum of Mountain Triplets I is classified as an Easy problem on LeetCode. The main challenge is recognizing that prefix and suffix minimum preprocessing can replace the naive O(n^3) triplet search with a linear-time scan.
Minimum Sum of Mountain Triplets I Python/Java solution
The optimal implementation in Python or Java uses a prefix minimum array and a reverse traversal for suffix minimum tracking. Each index is evaluated once, resulting in O(n) time complexity and O(n) auxiliary space.
How to solve Minimum Sum of Mountain Triplets I in O(n)?
Perform two linear passes. First compute a prefix minimum array where each index stores the smallest value to its left. Then iterate from right to left while tracking the smallest value on the right. For each index j, if both sides contain values smaller than nums[j], compute the candidate triplet sum and update the minimum.
What is the best approach for Minimum Sum of Mountain Triplets I?
The optimal approach uses a two-pass scan with prefix and suffix minimum values. Precompute the smallest value to the left of every index, then scan from the right while maintaining the minimum value on the right side. This allows evaluating each index as the mountain peak in O(1) time, producing an overall O(n) time and O(n) space solution.
Is Minimum Sum of Mountain Triplets I asked at Google/Amazon/Meta?
Problems involving triplets, prefix minimums, and array scanning patterns frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact question may vary, the technique of preprocessing left and right information for each index is a common interview pattern.
What data structure is used in Minimum Sum of Mountain Triplets I?
The solution primarily uses arrays. A prefix minimum array stores the smallest element to the left of each index, and a running suffix minimum tracks the smallest value on the right during traversal. No advanced data structures are required.
What is the time complexity of Minimum Sum of Mountain Triplets I?
The brute force approach takes O(n^3) time because it checks every possible triplet (i, j, k). The optimized solution reduces this to O(n) time by precomputing prefix minimums and maintaining a running suffix minimum during a second pass through the array.