Minimum Sum of Mountain Triplets I

Difficulty: Easy | Acceptance: 67.40% | Paid: No Topics: Array

You are given a 0-indexed array nums of integers.

A triplet of indices (i, j, k) is a mountain triplet if the following conditions are met:

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.

• Examples
• Constraints
• Brute Force
• Two-Pass
• Precompute Min Arrays

Examples

Example 1

Input: nums = [8,6,1,5,3]
Output: 9
Explanation: One mountain triplet is (2, 3, 4) with sum 1 + 5 + 3 = 9.

Example 2

Input: nums = [5,4,8,7,10,2]
Output: 14
Explanation: One mountain triplet is (1, 2, 5) with sum 4 + 8 + 2 = 14.

Example 3

Input: nums = [6,5,4,3,2,1]
Output: -1
Explanation: No mountain triplet exists.

Constraints

3 <= nums.length <= 50
1 <= nums[i] <= 50

Brute Force

Intuition Check all possible triplets (i, j, k) where i < j < k and verify if they form a mountain triplet. Track the minimum sum found.

Steps

• Iterate through all possible i, j, k combinations where i < j < k
• For each triplet, check if nums[i] < nums[j] and nums[k] < nums[j]
• If valid, update the minimum sum
• Return the minimum sum or -1 if no valid triplet exists

from typing import List

class Solution:
    def minimumSum(self, nums: List[int]) -> int:
        n = len(nums)
        min_sum = float('inf')
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    if nums[i] < nums[j] and nums[k] < nums[j]:
                        min_sum = min(min_sum, nums[i] + nums[j] + nums[k])
        return min_sum if min_sum != float('inf') else -1

Complexity

• Time: O(n³)
• Space: O(1)
• Notes: Simple but inefficient for larger arrays

Two-Pass

Intuition For each middle element j, find the minimum valid element to its left and right by scanning, then calculate the sum.

Steps

• For each index j from 1 to n-2
• Scan all elements to the left of j to find the minimum element less than nums[j]
• Scan all elements to the right of j to find the minimum element less than nums[j]
• If both exist, update the minimum sum
• Return the minimum sum or -1 if no valid triplet exists

from typing import List

class Solution:
    def minimumSum(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 3:
            return -1
        
        min_sum = float('inf')
        
        for j in range(1, n - 1):
            left_min = float('inf')
            for i in range(j):
                if nums[i] < nums[j]:
                    left_min = min(left_min, nums[i])
            
            right_min = float('inf')
            for k in range(j + 1, n):
                if nums[k] < nums[j]:
                    right_min = min(right_min, nums[k])
            
            if left_min != float('inf') and right_min != float('inf'):
                min_sum = min(min_sum, left_min + nums[j] + right_min)
        
        return min_sum if min_sum != float('inf') else -1

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Better than brute force but still not optimal

Precompute Min Arrays

Intuition Precompute the minimum element to the left and right of each index. If the minimum to the left is less than nums[j] and the minimum to the right is less than nums[j], we have a valid triplet.

Steps

• Create left_min array where left_min[i] stores the minimum element from index 0 to i-1
• Create right_min array where right_min[i] stores the minimum element from index i+1 to n-1
• For each middle index j, check if left_min[j] < nums[j] and right_min[j] < nums[j]
• If valid, calculate the sum and track the minimum
• Return the minimum sum or -1 if no valid triplet exists

from typing import List

class Solution:
    def minimumSum(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 3:
            return -1
        
        left_min = [float('inf')] * n
        right_min = [float('inf')] * n
        
        for i in range(1, n):
            left_min[i] = min(left_min[i - 1], nums[i - 1])
        
        for i in range(n - 2, -1, -1):
            right_min[i] = min(right_min[i + 1], nums[i + 1])
        
        min_sum = float('inf')
        for j in range(1, n - 1):
            if left_min[j] < nums[j] and right_min[j] < nums[j]:
                min_sum = min(min_sum, left_min[j] + nums[j] + right_min[j])
        
        return min_sum if min_sum != float('inf') else -1

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Optimal time complexity with trade-off of extra space