We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Sum of Mountain Triplets II

Number: 3186

Difficulty: Medium

Paid? No

Companies: ION

Problem Description

Given an array of integers, a mountain triplet is a triple of indices (i, j, k) with i < j < k that satisfies nums[i] < nums[j] and nums[k] < nums[j]. The task is to return the minimum possible sum nums[i] + nums[j] + nums[k] over all mountain triplets. If no mountain triplet exists, return -1.

Key Insights

  • For any candidate peak at index j (with 0 < j < n – 1), we need a candidate from the left (i) with nums[i] < nums[j] and a candidate from the right (k) with nums[k] < nums[j].
  • To minimize the overall sum, for each j we want the minimal valid number on its left (i) and on its right (k).
  • A single linear scan from left to right can maintain a running minimum from all indices before j to quickly determine the minimal candidate on the left.
  • A reverse scan from right to left can similarly provide the minimal candidate from indices after j.
  • Finally, iterate through each possible j and compute the triplet sum if both candidates exist. The minimum among these sums is the answer.

Space and Time Complexity

Time Complexity: O(n) – we perform two linear passes over the array plus a final iteration. Space Complexity: O(n) – extra arrays are used to store the best candidate from the left and right for each index.

Solution

The solution involves three main steps:

  1. Create an array (or similar structure) to store the minimum candidate to the left for each index j. Iterate left-to-right, keeping track of the smallest element seen so far. At each index j, if this running minimum is less than nums[j], it is the candidate.
  2. Create another array to store the minimum candidate to the right for each index j. Iterate right-to-left, similarly maintaining a running minimum for indices after j.
  3. For every index j (acting as the mountain peak), if valid left and right candidates exist (i.e. they are less than nums[j]), calculate the sum and update the global minimum. If no valid mountain triplet is found, return -1.

The trick is that the overall minimum candidate from the left (or right) will always yield the minimum contribution to the triplet sum for a fixed j, making the approach both simple and efficient.

Code Solutions

# Python solution with detailed comments

def minMountainTripletSum(nums):
    n = len(nums)
    if n < 3:
        return -1

    # Arrays to store the smallest valid left candidate and right candidate for each j.
    left_candidate = [None] * n
    right_candidate = [None] * n

    # Left-to-right pass:
    # For each index j, we want the minimum number from indices < j that is smaller than nums[j].
    left_min = nums[0]  # first element is the only candidate for j>0
    # No valid left candidate for index 0.
    for j in range(1, n):
        # Check if the current running min is a valid candidate for index j.
        if left_min < nums[j]:
            left_candidate[j] = left_min
        # Update the running minimum with the current element.
        left_min = min(left_min, nums[j])
    
    # Right-to-left pass:
    # For each index j, we want the minimum number from indices > j that is smaller than nums[j].
    right_min = nums[-1]  # last element
    # No valid right candidate for last index.
    for j in range(n - 2, -1, -1):
        # Check if the current running min from the right is a valid candidate.
        if right_min < nums[j]:
            right_candidate[j] = right_min
        # Update the running minimum.
        right_min = min(right_min, nums[j])
    
    # Now iterate over each possible mountain peak j to find the minimum mountain sum.
    min_sum = float('inf')
    for j in range(1, n - 1):
        if left_candidate[j] is not None and right_candidate[j] is not None:
            current_sum = left_candidate[j] + nums[j] + right_candidate[j]
            min_sum = min(min_sum, current_sum)
    
    return min_sum if min_sum != float('inf') else -1

# Example usage:
# print(minMountainTripletSum([8,6,1,5,3]))  # Output: 9
← Back to All Questions