Minimum Sum of Mountain Triplets II

Problem 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.

Key Insights

• A mountain triplet requires three indices where the middle index has to be greater than both its neighboring indices.
• We need to efficiently find valid triplets while minimizing their sum.
• A brute-force approach would be inefficient due to the constraints, so a more optimal approach is necessary.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)

Solution

To solve the problem, we can use a two-pointer technique after fixing the middle element of the triplet. For each potential middle element nums[j], we need to find the smallest nums[i] (where i < j) and the smallest nums[k] (where k > j) that satisfy the mountain conditions. The algorithm proceeds as follows:

1. Initialize a variable to store the minimum sum, initially set to infinity.
2. For each index j from 1 to n-2 (where n is the length of nums):
   • Use a linear scan to find the smallest nums[i] for i < j such that nums[i] < nums[j].
   • Use another linear scan to find the smallest nums[k] for k > j such that nums[k] < nums[j].
3. If valid i and k are found, calculate the sum and update the minimum sum.
4. After checking all possible j, return the minimum sum if it was updated, otherwise return -1.

Code Solutions