Minimum Sum of Mountain Triplets II

MEDIUM

Description

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 <= 10⁵
1 <= nums[i] <= 10⁸

Approaches

Checkout 3 different approaches to solve Minimum Sum of Mountain Triplets II. Click on different approaches to view the approach and algorithm in detail.

Brute Force Enumeration

This approach involves checking every possible triplet of indices (i, j, k) to see if it forms a mountain triplet. It's the most straightforward but also the least efficient method, serving as a baseline.

Algorithm

Initialize minSum to a very large value (e.g., Long.MAX_VALUE).
Use a first loop to iterate through index i from 0 to n-3.
Inside, use a second loop to iterate through index j from i+1 to n-2.
Inside the second loop, use a third loop to iterate through index k from j+1 to n-1.
In the innermost loop, check if the triplet (i, j, k) forms a mountain: nums[i] < nums[j] and nums[k] < nums[j].
If it is a mountain, calculate the sum nums[i] + nums[j] + nums[k] and update minSum with the minimum value seen so far.
After all loops complete, if minSum remains at its initial large value, no mountain triplet was found, so return -1.
Otherwise, return the minSum.

We use three nested loops to generate all combinations of i, j, and k such that 0 <= i < j < k < n, where n is the length of the array. For each triplet, we check if it satisfies the mountain conditions: nums[i] < nums[j] and nums[k] < nums[j]. If the conditions are met, we calculate the sum nums[i] + nums[j] + nums[k]. We keep track of the minimum sum found so far. If after checking all triplets, no mountain triplet has been found, we return -1. Otherwise, we return the minimum sum.

class Solution {
    public int minimumSum(int[] nums) {
        int n = nums.length;
        long minSum = Long.MAX_VALUE;
        boolean found = false;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] < nums[j] && nums[k] < nums[j]) {
                        minSum = Math.min(minSum, (long)nums[i] + nums[j] + nums[k]);
                        found = true;
                    }
                }
            }
        }

        return found ? (int)minSum : -1;
    }
}

Complexity Analysis

Time Complexity: O(n³), where n is the number of elements in `nums`. The three nested loops lead to a cubic time complexity, which is too slow for the problem's constraints (`n <= 10^5`).Space Complexity: O(1), as we only use a few variables to store the minimum sum and loop indices.

Pros and Cons

Pros:

Simple to understand and implement.
Correct for small input sizes.

Cons:

Extremely inefficient due to its cubic time complexity.
Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.

Code Solutions

Checking out 3 solutions in different languages for Minimum Sum of Mountain Triplets II. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Minimum Sum of Mountain Triplets II

Data Structures:

Array