Minimum Sum of Mountain Triplets II - Practice Coding Problems

Minimum Sum of Mountain Triplets II - Problem

Array Medium

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.

Input & Output

Example 1 — Basic Mountain

$ Input: nums = [8,6,1,5,3]

› Output: 9

💡 Note: Triplet (2,3,4) forms a mountain: nums[2]=1 < nums[3]=5 > nums[4]=3. Sum = 1+5+3 = 9.

Example 2 — Multiple Mountains

$ Input: nums = [5,4,8,7,10,2]

› Output: 13

💡 Note: Multiple valid mountains exist. Triplet (1,2,3) gives nums[1]=4 < nums[2]=8 > nums[3]=7. Sum = 4+8+7 = 19. But (1,4,5) gives 4 < 10 > 2 with sum = 16. Optimal is (0,4,5): 5 < 10 > 2 = 17. Actually, (1,2,5): 4 < 8 > 2 = 14. Best is (0,2,5): 5 < 8 > 2 = 15. Wait, let me recalculate: (1,4,5): 4 < 10 > 2 = 16, (0,4,5): 5 < 10 > 2 = 17, (1,2,5): 4 < 8 > 2 = 14, (0,2,5): 5 < 8 > 2 = 15, (1,2,3): 4 < 8 > 7 = 19. Minimum is 14.

Example 3 — No Mountain

$ Input: nums = [6,5,4,3,4,5]

› Output: -1

💡 Note: No valid mountain triplet exists. Elements either increase or decrease monotonically in segments, preventing mountain formation.

Constraints

3 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁸

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array with mountain pattern potential

Find Mountains

Identify triplets forming mountain shape

Minimum Sum

Return smallest sum among valid mountains

Key Takeaway

🎯 Key Insight: Use precomputed left/right minimums to efficiently find valid mountain triplets

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to use precomputation to avoid checking all triplets. For each potential peak position, we precompute the minimum values to its left and right. Best approach uses two-pass optimization with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Triplets	O(n³)	O(1)	Check every possible triplet (i,j,k) where i < j < k
Two-Pass Optimization	O(n)	O(n)	For each peak position, precompute minimum left and right values

Brute Force - Check All Triplets — Algorithm Steps

Iterate through all possible i positions
For each i, iterate through all j > i
For each j, iterate through all k > j
Check if nums[i] < nums[j] and nums[k] < nums[j]
Track minimum sum of valid mountain triplets

Visualization

Tap to expand

Step-by-Step Walkthrough

Triple Nested Loops

Check all combinations (i,j,k) where i < j < k

Mountain Check

Verify nums[i] < nums[j] and nums[k] < nums[j]

Track Minimum

Keep track of smallest valid sum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int* nums, int numsSize) {
    int minSum = INT_MAX;
    
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            for (int k = j + 1; k < numsSize; k++) {
                if (nums[i] < nums[j] && nums[k] < nums[j]) {
                    int sum = nums[i] + nums[j] + nums[k];
                    if (sum < minSum) {
                        minSum = sum;
                    }
                }
            }
        }
    }
    
    return minSum == INT_MAX ? -1 : minSum;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops each iterating up to n times

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Triplets — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler