Get started

Minimum Sum of Mountain Triplets II — Medium Problem & Solution

Indices i < j < k form a mountain triplet when nums[i] < nums[j] and nums[k] < nums[j] — the middle value is the peak.

  • Difficulty: Medium
  • Topics: Arrays, Prefix Sum
  • Asked at: Amazon, Google, Uber
  • 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 triplet when nums[i] < nums[j] and nums[k] < nums[j] — the middle value is the peak.

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

Example 1

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

Example 2

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

Example 3

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

Constraints

  • 3 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^8

How to solve Minimum Sum of Mountain Triplets II

Fix the peak. For a given middle index j, the cheapest triplet uses the smallest value to its left and the smallest to its right — so a prefix-minimum and a suffix-minimum array answer every peak in O(1).

Approach

  1. Build pre[j] = minimum of nums[0..j-1] and suf[j] = minimum of nums[j+1..n-1], both with a large sentinel where the side is empty.
  2. For each j from 1 to n-2, if pre[j] < nums[j] and suf[j] < nums[j], consider pre[j] + nums[j] + suf[j].
  3. Return the best sum found, or -1.

Why it works

Both flanks are chosen independently once the peak is fixed, so taking the minimum on each side is optimal — there is no interaction between the choice of i and of k beyond both being smaller than the peak. This is what turns the O(n³) triple loop of version I into one linear pass, which is what the larger n here demands.

Complexity

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

Pitfalls

  • The comparisons are strict: an equal neighbour does not make a mountain.
  • The sentinel must exceed every possible value, or an empty side would be mistaken for a valid flank.
  • Return -1, not 0, when no triplet exists.

Reference solution

Python

from typing import List

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

JavaScript

var minimumSum = function(nums) {
    var n = nums.length, INF = 2000000000, i;
    var pre = [], suf = [];
    for (i = 0; i < n; i++) { pre.push(INF); suf.push(INF); }
    var m = INF;
    for (i = 0; i < n; i++) { pre[i] = m; if (nums[i] < m) m = nums[i]; }
    m = INF;
    for (i = n - 1; i >= 0; i--) { suf[i] = m; if (nums[i] < m) m = nums[i]; }
    var best = -1;
    for (var j = 1; j < n - 1; j++) {
        if (pre[j] < nums[j] && suf[j] < nums[j]) {
            var s = pre[j] + nums[j] + suf[j];
            if (best === -1 || 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