Skip to main content
Talentd

Minimum Sum of Mountain Triplets II - Solution & Explanation

MediumArray19 min read
Practice this problem

Problem Statement

You are given a 0-indexed array nums of integers.

A triplet of indices (i, j, k) is a mountain if:

  • i < j < k
  • nums[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 <= 105
  • 1 <= 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.

This C solution iterates over each element considering it as a potential peak of the mountain triplet. Helper loops are used to determine the smallest valid elements on the left and right sides of each peak that satisfy the mountain property.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), where n is the size of the array.
Space Complexity: O(1), as we use a constant amount of additional space.

Try this approach in the editor →

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.

This C solution precomputes the smallest element to the left and right of each potential peak to avoid unnecessary traversals. This optimization significantly reduces time complexity.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Peak and Two-Pointer Strategy

Time Complexity: O(n^2), where n is the size of the array.
Space Complexity: O(1), as we use a constant amount of additional space.

Optimized Precomputation Method

Time Complexity: O(n)
Space Complexity: O(n)

Preprocessing + Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Peak and Two-Pointer StrategyO(n²)O(1)Useful for understanding the problem structure or when input size is small
Optimized Precomputation MethodO(n)O(n)Best choice for interviews and large arrays; avoids repeated scanning by using prefix and suffix minimums

Video Solution

Leetcode Weekly contest 368 - Easy & Medium - Minimum Sum of Mountain Triplets II & I • Prakhar Agrawal • 1,596 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Sum of Mountain Triplets II with our built-in code editor and test cases.

Practice on FleetCode
Previous

3Sum

Next

Maximum Value of an Ordered Triplet II