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 I

Number: 3176

Difficulty: Easy

Paid? No

Companies: ION

Problem Description

Given a 0-indexed array nums of integers, find three indices (i, j, k) such that i < j < k and they form a mountain pattern (nums[i] < nums[j] and nums[k] < nums[j]). Return the minimum possible sum (nums[i] + nums[j] + nums[k]) of such a triplet. If no valid mountain triplet exists, return -1.

Key Insights

  • The triplet must satisfy i < j < k with nums[i] < nums[j] and nums[k] < nums[j].
  • Since the array length is small (up to 50), a brute force triple nested loop checking all possible combinations is feasible.
  • Alternatively, one may precompute the minimum valid candidate on the left and right for each potential center index j to optimize the solution.
  • Always check that for a given j, there is at least one valid i and k, otherwise skip.

Space and Time Complexity

Time Complexity: O(n^3) in the brute-force approach (n <= 50, so it is acceptable) Space Complexity: O(1) extra space aside from the input variable

Solution

We use a brute-force approach by iterating over every possible triplet (i, j, k) such that i < j < k. For every candidate triplet, we check if nums[i] < nums[j] and nums[k] < nums[j]. If the condition holds, we update the minimum sum. Since the constraint allows for n up to 50, this approach is efficient enough. The trick here is to ensure that we only consider valid mountain triplets and handle cases where no valid triplet exists by returning -1.

Code Solutions

# Python solution for Minimum Sum of Mountain Triplets I

def minimumMountainSum(nums):
    n = len(nums)
    min_sum = float('inf')  # Initialize the minimum sum to infinity
    
    # Iterate over all possible triplets with i < j < k
    for j in range(1, n - 1):
        for i in range(j):
            if nums[i] >= nums[j]:
                continue  # Ensure left side is strictly less than the peak value
            for k in range(j + 1, n):
                if nums[k] >= nums[j]:
                    continue  # Ensure right side is strictly less than the peak value
                # Valid mountain triplet found, update the minimum sum if lower
                current_sum = nums[i] + nums[j] + nums[k]
                min_sum = min(min_sum, current_sum)
    
    # If min_sum remains infinity, no mountain triplet exists; return -1
    return -1 if min_sum == float('inf') else min_sum

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