Get started

Minimum Sum of Mountain Triplets I — Easy Problem & Solution

Indices i < j < k form a mountain when nums[i] < nums[j] and nums[k] < nums[j].

  • Difficulty: Easy
  • Topics: Arrays, Prefix Sum
  • Asked at: Amazon, Google, Mindtree
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Indices i < j < k form a mountain when nums[i] < nums[j] and nums[k] < nums[j].

Return the minimum possible value of nums[i] + nums[j] + nums[k] over all mountains, or -1 if there is none.

Example 1

Input: nums = [8,6,1,5,3]
Output: 9
Explanation: Indices 2, 3 and 4: `1 + 5 + 3`.

Example 2

Input: nums = [5,4,8,7,10,2]
Output: 13
Explanation: Indices 1, 3 and 5: `4 + 7 + 2`.

Example 3

Input: nums = [6,5,4,3,4,5]
Output: -1
Explanation: No index has a smaller value on both sides.

Constraints

  • 3 <= nums.length <= 50
  • 1 <= nums[i] <= 50

How to solve Minimum Sum of Mountain Triplets I

Treat each index as the peak. The cheapest mountain through it uses the smallest value on its left and the smallest on its right, so prefix and suffix minima answer every peak in O(1).

Approach

  1. Build pre[i] = the minimum of nums[0 … i] and suf[i] = the minimum of nums[i … n-1].
  2. For each j from 1 to n - 2, check pre[j-1] < nums[j] and suf[j+1] < nums[j].
  3. Track the smallest total; return -1 if no peak qualifies.

Why it works

Fixing the peak decouples the two sides — the choice of i never constrains k — which is what turns an O(n³) scan over triples into two linear passes. Both inequalities are strict, so a flat plateau never forms a mountain.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Both comparisons are strict; equal neighbours do not make a peak.
  • The first and last indices can never be the peak.
  • Return -1, not 0, when no mountain exists.

Reference solution

Python

from typing import List

def minimumSum(nums: List[int]) -> int:
    n = len(nums)
    pre = [0] * n
    suf = [0] * n
    pre[0] = nums[0]
    for i in range(1, n):
        pre[i] = min(pre[i - 1], nums[i])
    suf[n - 1] = nums[n - 1]
    for i in range(n - 2, -1, -1):
        suf[i] = min(suf[i + 1], nums[i])
    best = -1
    for j in range(1, n - 1):
        if pre[j - 1] < nums[j] and suf[j + 1] < nums[j]:
            s = pre[j - 1] + nums[j] + suf[j + 1]
            if best < 0 or s < best:
                best = s
    return best

JavaScript

var minimumSum = function(nums) {
    var n = nums.length, i;
    if (n < 3) return -1;
    var pre = [], suf = [];
    for (i = 0; i < n; i++) { pre.push(0); suf.push(0); }
    pre[0] = nums[0];
    for (i = 1; i < n; i++) pre[i] = Math.min(pre[i - 1], nums[i]);
    suf[n - 1] = nums[n - 1];
    for (i = n - 2; i >= 0; i--) suf[i] = Math.min(suf[i + 1], nums[i]);
    var best = -1;
    for (var j = 1; j + 1 < n; j++) {
        if (pre[j - 1] < nums[j] && suf[j + 1] < nums[j]) {
            var s = pre[j - 1] + nums[j] + suf[j + 1];
            if (best < 0 || s < best) best = s;
        }
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue