Skip to main content
Talentd

Minimum Sum of Mountain Triplets I - Solution & Explanation

EasyArray19 min readAsked at: Microsoft
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 <= 50
  • 1 <= 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).

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^3)
Space Complexity: O(1)

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2)
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
Brute Force Approach

Time Complexity: O(n^3)
Space Complexity: O(1)

Optimized Two-Pass Approach

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

Preprocessing + Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n^3)O(1)Small arrays or when explaining the baseline logic in interviews
Two-Pass Prefix & Suffix MinimumO(n)O(n)General case; optimal approach expected in coding interviews

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 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.

Ready to solve this problem?

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

Practice on FleetCode
Previous

3Sum

Next

Maximum Value of an Ordered Triplet I