Problem Description

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

A triplet of indices (i, j, k) forms a mountain if:

• The indices are in strictly increasing order: i < j < k
• The middle element is the peak: nums[i] < nums[j] and nums[k] < nums[j]

In other words, nums[j] must be greater than both nums[i] and nums[k], creating a mountain-like pattern where the value rises from position i to j, then falls from j to k.

Your task is to find the minimum possible sum of any mountain triplet in the array. The sum of a mountain triplet (i, j, k) is calculated as nums[i] + nums[j] + nums[k].

If no valid mountain triplet exists in the array, return -1.

For example:

• If nums = [8, 6, 1, 5, 3], a valid mountain triplet is (2, 3, 4) with values (1, 5, 3), where 1 < 5 > 3. The sum would be 1 + 5 + 3 = 9.
• If nums = [5, 4, 3, 2, 1], no mountain triplet exists since the array is strictly decreasing.

Intuition

To find the minimum sum of a mountain triplet, we need three elements where the middle one is the peak. The key insight is that for each potential peak element, we want to find the smallest element on its left and the smallest element on its right.

Think about it this way: if we fix the middle element nums[j] as our peak, then to minimize the total sum, we need:

• The smallest possible nums[i] where i < j and nums[i] < nums[j]
• The smallest possible nums[k] where k > j and nums[k] < nums[j]

A brute force approach would check all possible triplets, which takes O(n³) time. But we can optimize this by recognizing that for each potential peak position, we don't need to check all elements - we just need the minimum values on each side.

The challenge is efficiently finding these minimum values. For the left side, we can maintain a running minimum as we traverse the array. But for the right side, we need to know the minimum value after each position before we start our main traversal.

This leads us to a two-pass approach:

1. First pass (right to left): Precompute the minimum value to the right of each position. Store this in an array right[i] where right[i] represents the minimum value in nums[i+1..n-1].

2. Second pass (left to right): For each position j, check if it can be a valid peak by comparing it with the minimum on its left (maintained as we go) and the minimum on its right (from our precomputed array). If left_min < nums[j] > right_min, we have a valid mountain, and we can calculate its sum.

This approach reduces the time complexity to O(n) with O(n) extra space, making it much more efficient than checking all triplets.

Solution Approach

Let's implement the solution step by step based on our intuition:

Step 1: Preprocess right minimums

First, we create an array right of size n+1 to store the minimum values to the right of each position. We initialize it with infinity values.

right = [inf] * (n + 1)
for i in range(n - 1, -1, -1):
    right[i] = min(right[i + 1], nums[i])

We traverse from right to left (indices n-1 to 0). For each position i, right[i] stores the minimum of:

• right[i + 1]: the minimum value to the right of position i+1
• nums[i]: the current element

This way, right[i] contains the minimum value in nums[i..n-1], and right[i+1] contains the minimum value in nums[i+1..n-1].

Step 2: Find the minimum mountain sum

Now we traverse the array from left to right, treating each element as a potential peak:

ans = left = inf
for i, x in enumerate(nums):
    if left < x and right[i + 1] < x:
        ans = min(ans, left + x + right[i + 1])
    left = min(left, x)

During this traversal:

• left maintains the minimum value seen so far (to the left of current position)
• x is the current element nums[i], which we consider as the potential peak
• right[i + 1] gives us the minimum value to the right of position i

For each position i, we check if it can form a valid mountain:

• left < x: there exists a smaller element on the left
• right[i + 1] < x: there exists a smaller element on the right

If both conditions are satisfied, we have a valid mountain triplet with sum left + x + right[i + 1]. We update ans with the minimum sum found so far.

After checking position i as a peak, we update left to include the current element for future iterations.

Step 3: Return the result

return -1 if ans == inf else ans

If ans remains as infinity, it means no valid mountain triplet was found, so we return -1. Otherwise, we return the minimum sum found.

Time Complexity: O(n) - two passes through the array
Space Complexity: O(n) - for the right array

Example Walkthrough

Let's walk through the solution with nums = [8, 6, 1, 5, 3]:

Step 1: Build the right minimum array

We traverse from right to left to build right[]:

• Start with right = [inf, inf, inf, inf, inf, inf]
• i=4: right[4] = min(right[5], nums[4]) = min(inf, 3) = 3
• i=3: right[3] = min(right[4], nums[3]) = min(3, 5) = 3
• i=2: right[2] = min(right[3], nums[2]) = min(3, 1) = 1
• i=1: right[1] = min(right[2], nums[1]) = min(1, 6) = 1
• i=0: right[0] = min(right[1], nums[0]) = min(1, 8) = 1

Final right = [1, 1, 1, 3, 3, inf]

This means:

• right[1] = 1: minimum in nums[1..4] is 1
• right[2] = 1: minimum in nums[2..4] is 1
• right[3] = 3: minimum in nums[3..4] is 3
• right[4] = 3: minimum in nums[4..4] is 3

Step 2: Find minimum mountain sum

Now traverse left to right, checking each position as a potential peak:

• i=0, nums[0]=8:

  • left = inf, right[1] = 1
  • Check: inf < 8? No, so not a valid peak
  • Update: left = min(inf, 8) = 8

• i=1, nums[1]=6:

  • left = 8, right[2] = 1
  • Check: 8 < 6? No, so not a valid peak
  • Update: left = min(8, 6) = 6

• i=2, nums[2]=1:

  • left = 6, right[3] = 3
  • Check: 6 < 1? No, so not a valid peak
  • Update: left = min(6, 1) = 1

• i=3, nums[3]=5:

  • left = 1, right[4] = 3
  • Check: 1 < 5 AND 3 < 5? Yes! Valid mountain
  • Sum = 1 + 5 + 3 = 9
  • Update: ans = min(inf, 9) = 9, left = min(1, 5) = 1

• i=4, nums[4]=3:

  • left = 1, right[5] = inf
  • Check: 1 < 3 AND inf < 3? No, so not a valid peak
  • Update: left = min(1, 3) = 1

Step 3: Return result

ans = 9, so we return 9.

The mountain triplet found is (2, 3, 4) with values (1, 5, 3), giving the minimum sum of 9.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array.

• The first loop iterates from n-1 to 0, performing O(1) operations in each iteration, contributing O(n) time.
• The second loop iterates through all n elements of the array using enumerate(), performing O(1) operations (comparisons and min operations) in each iteration, contributing O(n) time.
• Total time complexity: O(n) + O(n) = O(n)

The space complexity is O(n), where n is the length of the array.

• The right array is initialized with size n + 1, requiring O(n) space.
• Other variables (ans, left, i, x) use constant space O(1).
• Total space complexity: O(n) + O(1) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Off-by-One Error with Right Minimum Array

The Problem: A common mistake is incorrectly indexing the min_right array when checking for valid mountains. Developers often write:

if min_left < current_value and min_right[i] < current_value:  # WRONG!

This is incorrect because min_right[i] includes the current element itself. Since we need the minimum value strictly to the right of position i, we must use min_right[i + 1].

Why This Happens:

• Confusion about what min_right[i] represents
• Not clearly distinguishing between "from index i" vs "after index i"

Solution: Always use min_right[i + 1] when checking for elements to the right of position i:

if min_left < current_value and min_right[i + 1] < current_value:  # CORRECT

Pitfall 2: Incorrect Initialization of Left Minimum

The Problem: Some developers initialize min_left with the first element of the array:

min_left = nums[0]  # WRONG!
for i in range(1, n):
    # check for mountain at position i

This prevents the first element from ever being considered as a potential peak, even if valid mountains exist with index 0 as the peak.

Why This Happens:

• Assumption that we need at least one element on the left before checking
• Misunderstanding that the left minimum should be updated after checking each position

Solution: Initialize min_left with infinity and update it after checking each position:

min_left = float('inf')
for i, current_value in enumerate(nums):
    # First check if current can be a peak
    if min_left < current_value and min_right[i + 1] < current_value:
        # Process valid mountain
    # Then update min_left for next iterations
    min_left = min(min_left, current_value)

Pitfall 3: Using the Actual Minimum Values Instead of Just Tracking Them

The Problem: Attempting to store actual indices or trying to find the exact elements that form the mountain:

left_min_index = -1
right_min_index = -1
# Trying to track which elements form the triplet

This overcomplicates the solution since we only need the minimum possible sum, not the actual triplet indices.

Why This Happens:

• Over-interpreting the problem requirements
• Confusion between finding the minimum sum vs finding the actual triplet

Solution: Focus only on tracking minimum values, not their positions:

# We only need values, not indices
min_left = float('inf')  # Just the value
min_right[i]  # Just the minimum value to the right

Pitfall 4: Forgetting Edge Cases

The Problem: Not handling arrays that are too small to form a mountain:

# Forgetting to check if n < 3
def minimumSum(self, nums):
    n = len(nums)
    # Proceeds without checking if mountain is possible

Solution: Add an early check for arrays with fewer than 3 elements:

def minimumSum(self, nums):
    n = len(nums)
    if n < 3:
        return -1  # Cannot form a mountain with less than 3 elements