Problem Description

You are given a 0-indexed array nums of integers. Your task is to find three elements that form a "mountain" pattern.

A mountain triplet consists of three indices (i, j, k) where:

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

In other words, you need to find three elements where the middle element is strictly greater than both the left and right elements, forming a peak like a mountain.

Your goal is to find such a mountain triplet that has the minimum possible sum (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 could be indices (2, 3, 4) with values (1, 5, 3), where 1 < 5 > 3, giving a sum of 1 + 5 + 3 = 9.
• If nums = [5, 4, 3, 2, 1], no mountain triplet exists since the array is strictly decreasing, so the answer would be -1.

The challenge is to efficiently find the mountain triplet with the smallest sum among all possible valid triplets.

Intuition

To find the minimum sum of a mountain triplet, we need to think about what makes a valid mountain and how to minimize its sum.

For any middle element nums[j] to be the peak of a mountain, we need:

• An element to its left that is smaller than nums[j]
• An element to its right that is smaller than nums[j]

To minimize the total sum, we want to choose the smallest possible values for both the left and right elements. This leads us to a key insight: for each potential peak position j, we should pick the minimum value from all elements to its left and the minimum value from all elements to its right (as long as both are smaller than nums[j]).

The brute force approach would be to check every possible triplet, which would take O(n³) time. However, we can optimize this by fixing the middle element and finding the best left and right elements for it.

If we iterate through each position as a potential peak, we need to quickly know:

1. What's the smallest element to the left of current position?
2. What's the smallest element to the right of current position?

For the left side, we can maintain a running minimum as we traverse from left to right. For the right side, we can precompute the minimum values for all positions by traversing the array from right to left once.

This preprocessing approach allows us to check each potential peak in O(1) time after O(n) preprocessing, giving us an overall O(n) solution. We simply iterate through each position, check if it can be a valid peak (by comparing with the minimum on its left and right), and if valid, calculate the sum and update our answer if it's smaller than what we've found so far.

Solution Approach

The solution implements the preprocessing and enumeration strategy to find the minimum mountain triplet sum efficiently.

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 and traverse the array from right to left:

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

After this preprocessing, right[i] contains the minimum value among all elements from index i to the end of the array. Specifically, right[i+1] gives us the minimum value to the right of position i.

Step 2: Enumerate Middle Elements

We then traverse the array from left to right, considering each element as a potential peak of the mountain. We maintain two variables:

• left: tracks the minimum value seen so far (to the left of current position)
• ans: stores the minimum mountain triplet sum found so far

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)

For each position i with value x = nums[i], we check if it can be a valid peak:

• Is there a smaller element to its left? (left < x)
• Is there a smaller element to its right? (right[i + 1] < x)

If both conditions are met, we have a valid mountain triplet with sum left + x + right[i + 1]. We update ans if this sum is smaller than the current minimum.

After checking position i as a potential peak, we update left to include the current element, maintaining the minimum value seen so far.

Step 3: Return Result

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

return -1 if ans == inf else ans

The time complexity is O(n) for both the preprocessing and the main enumeration, and the space complexity is 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 create a right array to store the minimum value to the right of each position:

• Start with right = [inf, inf, inf, inf, inf, inf] (size n+1 = 6)
• Traverse from right to left:
  • i=4: right[4] = min(inf, 3) = 3
  • i=3: right[3] = min(3, 5) = 3
  • i=2: right[2] = min(3, 1) = 1
  • i=1: right[1] = min(1, 6) = 1
  • i=0: right[0] = min(1, 8) = 1
• Result: right = [1, 1, 1, 3, 3, inf]

Step 2: Enumerate each position as a potential peak

Initialize ans = inf and left = inf.

• Position 0 (x = 8):

  • Check: left (inf) < 8? No, so this can't be a peak
  • Update: left = min(inf, 8) = 8

• Position 1 (x = 6):

  • Check: left (8) < 6? No, so this can't be a peak
  • Update: left = min(8, 6) = 6

• Position 2 (x = 1):

  • Check: left (6) < 1? No, so this can't be a peak
  • Update: left = min(6, 1) = 1

• Position 3 (x = 5):

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

• Position 4 (x = 3):

  • Check: left (1) < 3? Yes! right[5] (inf) < 3? No
  • Not a valid peak (no element to the right)
  • Update: left = min(1, 3) = 1

Step 3: Return the result

Since ans = 9 (not infinity), we return 9.

The mountain triplet with minimum sum is at indices (2, 3, 4) with values (1, 5, 3).

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the input array nums. This is because:

• The first loop iterates through the array once from right to left to build the right array, taking O(n) time
• The second loop iterates through the array once from left to right to find the minimum sum, taking O(n) time
• All operations inside both loops (comparisons, min operations, assignments) take O(1) time
• Total time complexity: O(n) + O(n) = O(n)

The space complexity is O(n), where n is the length of the input array. This is because:

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

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

Common Pitfalls

1. Incorrect Index Handling for Right Minimum Array

Pitfall: A common mistake is misaligning the indices when accessing the min_right array. Developers often use min_right[i] instead of min_right[i + 1] when checking for the minimum value to the right of position i.

Why it happens: The confusion arises because min_right[i] stores the minimum from index i onwards (including i itself), but for a valid mountain triplet, we need the minimum strictly to the right of i (excluding i).

Incorrect implementation:

# Wrong: This includes nums[i] in the right minimum
if min_left < current_num and min_right[i] < current_num:
    triplet_sum = min_left + current_num + min_right[i]

Correct implementation:

# Correct: This excludes nums[i] from the right minimum
if min_left < current_num and min_right[i + 1] < current_num:
    triplet_sum = min_left + current_num + min_right[i + 1]

2. Not Handling Edge Cases Properly

Pitfall: Failing to handle arrays that are too small (length < 3) or forgetting to initialize variables with infinity values, leading to incorrect comparisons.

Solution: Always check array length and use proper initialization:

if n < 3:
    return -1
  
min_sum = float('inf')  # Not 0 or any finite number
min_left = float('inf')  # Must start with infinity

3. Including Current Element in Left Minimum Too Early

Pitfall: Updating min_left before checking if the current element can be a peak, which would allow the same element to be both the left minimum and the peak.

Incorrect order:

for i, current_num in enumerate(nums):
    min_left = min(min_left, current_num)  # Wrong: Updated too early
    if min_left < current_num and min_right[i + 1] < current_num:
        # This check might fail incorrectly

Correct order:

for i, current_num in enumerate(nums):
    if min_left < current_num and min_right[i + 1] < current_num:
        # Check first with the previous min_left
    min_left = min(min_left, current_num)  # Update after checking

4. Using the Wrong Comparison Operators

Pitfall: Using <= instead of < for comparisons, which would allow equal values in the triplet, violating the strict inequality requirement for a mountain pattern.

Solution: Always use strict inequalities (<) to ensure the peak is strictly greater than both sides:

# Must be strict inequalities for a valid mountain
if min_left < current_num and min_right[i + 1] < current_num: