Minimum Sum of Mountain Triplets II

Medium
1004.

Minimum Sum of Mountain Triplets II

Minimum Sum of Mountain Triplets II is a medium coding problem on arrays and prefix sum, asked in Amazon, Google and Uber interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumSum = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Sum of Mountain Triplets II — Problem & Solution

Minimum Sum of Mountain Triplets II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Sum of Mountain Triplets II is a medium coding problem on arrays and prefix sum, asked in Amazon, Google and Uber interviews.

  • 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

Hints for Minimum Sum of Mountain Triplets II

  1. Hint 1

    Fix the peak j. The best i is the smallest value strictly left of j, and the best k the smallest strictly right.

  2. Hint 2

    Precompute a prefix minimum and a suffix minimum so each peak is answered in constant time.

  3. Hint 3

    Only accept a peak whose two minima are strictly smaller than it.

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

Java

public static int minimumSum(int[] nums) {
    int n = nums.length;
    final int INF = 2000000000;
    int[] pre = new int[n];
    int[] suf = new int[n];
    int m = INF;
    for (int i = 0; i < n; i++) {
        pre[i] = m;
        m = Math.min(m, nums[i]);
    }
    m = INF;
    for (int i = n - 1; i >= 0; i--) {
        suf[i] = m;
        m = Math.min(m, nums[i]);
    }
    int best = -1;
    for (int j = 1; j < n - 1; j++) {
        if (pre[j] < nums[j] && suf[j] < nums[j]) {
            int s = pre[j] + nums[j] + suf[j];
            if (best == -1 || s < best) best = s;
        }
    }
    return best;
}

C++

int minimumSum(vector<int>& nums) {
    int n = (int) nums.size();
    const int INF = 2000000000;
    vector<int> pre(n, INF), suf(n, INF);
    int m = INF;
    for (int i = 0; i < n; i++) {
        pre[i] = m;
        m = min(m, nums[i]);
    }
    m = INF;
    for (int i = n - 1; i >= 0; i--) {
        suf[i] = m;
        m = min(m, nums[i]);
    }
    int best = -1;
    for (int j = 1; j < n - 1; j++) {
        if (pre[j] < nums[j] && suf[j] < nums[j]) {
            int s = pre[j] + nums[j] + suf[j];
            if (best == -1 || 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Prefix Sum