Minimum Sum of Mountain Triplets I

Easy
988.

Minimum Sum of Mountain Triplets I

Minimum Sum of Mountain Triplets I is an easy coding problem on arrays and prefix sum, asked in Amazon, Google and Mindtree interviews.

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
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 I — Problem & Solution

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

Minimum Sum of Mountain Triplets I is an easy coding problem on arrays and prefix sum, asked in Amazon, Google and Mindtree interviews.

  • 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

Hints for Minimum Sum of Mountain Triplets I

  1. Hint 1

    Fix the peak j and the other two choices become independent.

  2. Hint 2

    The best i is the smallest value to the left, and the best k the smallest to the right.

  3. Hint 3

    Precompute prefix and suffix minima in one pass each.

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

Java

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

C++

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

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Prefix Sum