Scale Engineer

Minimum Sum of Mountain Triplets I

Easy
#2589Time: O(n³), where n is the length of the `nums` array. The three nested loops lead to a cubic number of operations, as we check every possible triplet.Space: O(1), as we only use a constant amount of extra space for variables like `minSum` and loop counters.
Data structures
Array

Prompt

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.

 

Example 1:

Input: nums = [8,6,1,5,3]
Output: 9
Explanation: Triplet (2, 3, 4) is a mountain triplet of sum 9 since: 
- 2 < 3 < 4
- nums[2] < nums[3] and nums[4] < nums[3]
And the sum of this triplet is nums[2] + nums[3] + nums[4] = 9. It can be shown that there are no mountain triplets with a sum of less than 9.

Example 2:

Input: nums = [5,4,8,7,10,2]
Output: 13
Explanation: Triplet (1, 3, 5) is a mountain triplet of sum 13 since: 
- 1 < 3 < 5
- nums[1] < nums[3] and nums[5] < nums[3]
And the sum of this triplet is nums[1] + nums[3] + nums[5] = 13. It can be shown that there are no mountain triplets with a sum of less than 13.

Example 3:

Input: nums = [6,5,4,3,4,5]
Output: -1
Explanation: It can be shown that there are no mountain triplets in nums.

 

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly translates the problem definition into code. It involves using three nested loops to iterate through all possible triplets of indices (i, j, k) such that i < j < k. For each triplet, it checks if it satisfies the mountain condition (nums[i] < nums[j] and nums[k] < nums[j]). If it does, the sum of the triplet's values is calculated and compared with the minimum sum found so far.

Algorithm

    1. Initialize a variable minSum to a very large value (e.g., Integer.MAX_VALUE) and a boolean flag found to false.
    1. Use a loop to iterate through each possible index i from 0 to n-3.
    1. Inside this loop, nest another loop to iterate through each possible index j from i+1 to n-2.
    1. Inside the second loop, nest a third loop to iterate through each possible index k from j+1 to n-1.
    1. For each triplet of indices (i, j, k), check if it forms a mountain: nums[i] < nums[j] and nums[k] < nums[j].
    1. If the condition is true, calculate the sum currentSum = nums[i] + nums[j] + nums[k].
    1. Update minSum = Math.min(minSum, currentSum) and set found to true.
    1. After all loops complete, if found is true, return minSum. Otherwise, return -1.

Walkthrough

The brute-force method is the most straightforward way to solve the problem. We systematically check every possible combination of three distinct indices i, j, and k that satisfy the i < j < k ordering.

We can achieve this with three nested loops. The outermost loop picks the first element nums[i], the middle loop picks the second element nums[j], and the innermost loop picks the third element nums[k]. Inside the innermost loop, we have a triplet and can check if it meets the mountain criteria. If it does, we compute its sum and update our minimum sum if the current sum is smaller. We use a variable, initialized to a very large number, to keep track of this minimum sum. If, after checking all triplets, this variable hasn't changed, it means no mountain triplet exists, and we should return -1.

class Solution {    public int minimumSum(int[] nums) {        int n = nums.length;        int minSum = Integer.MAX_VALUE;        boolean found = false;         for (int i = 0; i < n - 2; i++) {            for (int j = i + 1; j < n - 1; j++) {                for (int k = j + 1; k < n; k++) {                    if (nums[i] < nums[j] && nums[k] < nums[j]) {                        minSum = Math.min(minSum, nums[i] + nums[j] + nums[k]);                        found = true;                    }                }            }        }         return found ? minSum : -1;    }}

Complexity

Time

O(n³), where n is the length of the `nums` array. The three nested loops lead to a cubic number of operations, as we check every possible triplet.

Space

O(1), as we only use a constant amount of extra space for variables like `minSum` and loop counters.

Trade-offs

Pros

  • Simple to understand and implement.

  • Directly follows the problem statement without complex logic.

Cons

  • Highly inefficient due to its O(n³) time complexity.

  • Will be too slow for larger input constraints, although it passes for the given constraints (n <= 50).

Solutions

class Solution {public  int minimumSum(int[] nums) {    int n = nums.length;    int[] right = new int[n + 1];    final int inf = 1 << 30;    right[n] = inf;    for (int i = n - 1; i >= 0; --i) {      right[i] = Math.min(right[i + 1], nums[i]);    }    int ans = inf, left = inf;    for (int i = 0; i < n; ++i) {      if (left < nums[i] && right[i + 1] < nums[i]) {        ans = Math.min(ans, left + nums[i] + right[i + 1]);      }      left = Math.min(left, nums[i]);    }    return ans == inf ? -1 : ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem