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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Sum of Mountain Triplets I

Difficulty: Easy

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 element is greater than the other two.
  • The problem can be solved by iterating through possible middle elements and checking conditions for potential triplets.
  • We can maintain a minimum sum while ensuring the triplet conditions are met.

Space and Time Complexity

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

Solution

To solve the problem, we can use a brute-force approach that involves three nested loops to examine all possible triplets (i, j, k). For each valid middle index j, we will look for indices i and k such that:

  • i < j < k
  • nums[i] < nums[j] and nums[k] < nums[j]

If these conditions are met, we will calculate the sum of the triplet and update the minimum sum found. If no valid triplets are found, we return -1.

Code Solutions

def minimum_sum_mountain_triplet(nums):
    n = len(nums)
    min_sum = float('inf')
    found = False

    for j in range(1, n - 1):
        for i in range(0, j):
            for k in range(j + 1, n):
                if nums[i] < nums[j] and nums[k] < nums[j]:
                    found = True
                    current_sum = nums[i] + nums[j] + nums[k]
                    min_sum = min(min_sum, current_sum)

    return min_sum if found else -1
← Back to All Questions