LeetCode 2909 - Minimum Sum of Mountain Triplets II

The problem asks us to find three indices (i, j, k) such that the middle element forms the peak of a mountain. More specifically, the indices must satisfy: - i < j < k - nums[i] < nums[j] - nums[k] < nums[j] Among all valid mountain triplets, we must return the minimum…

leetcodemediumarray

LeetCode Problem 2909

Difficulty: 🟡 Medium
Topics: Array

Solution

Problem Understanding

The problem asks us to find three indices (i, j, k) such that the middle element forms the peak of a mountain. More specifically, the indices must satisfy:

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

Among all valid mountain triplets, we must return the minimum possible value of:

$$nums[i] + nums[j] + nums[k]$$

If no valid mountain triplet exists, we return -1.

The input is a single integer array nums. The array can contain up to 10^5 elements, which immediately tells us that cubic or even quadratic solutions may be too slow. Since each value can be as large as 10^8, we also need to be careful to avoid assumptions about small numeric ranges.

The important detail is that the middle element nums[j] must be strictly greater than at least one element on its left and at least one element on its right. We are not asked to find the longest mountain or count mountains, only the minimum sum among all valid triplets.

Several edge cases are important:

  • Arrays that are entirely increasing or entirely decreasing cannot form a mountain.
  • Duplicate values do not satisfy the strict inequality condition.
  • The smallest valid array size is 3, so a single triplet may be the only candidate.
  • The minimum sum does not necessarily involve the smallest middle value, because the left and right values also contribute to the total.

Approaches

Brute Force Approach

The most direct solution is to try every possible triplet (i, j, k) where i < j < k.

For each triplet:

  1. Check whether nums[i] < nums[j]
  2. Check whether nums[k] < nums[j]
  3. If both conditions hold, compute the sum
  4. Keep track of the minimum valid sum

This approach is guaranteed to find the correct answer because it exhaustively checks every possible triplet.

However, the time complexity is extremely large. With n up to 10^5, a triple nested loop would require:

$$O(n^3)$$

operations, which is far beyond practical limits.

Key Insight for the Optimal Solution

The important observation is that for every possible middle index j, we only care about:

  • The smallest valid value to the left of j
  • The smallest valid value to the right of j

Why? Because minimizing the triplet sum means we should always choose the smallest possible valid partner on each side.

So instead of checking all triplets, we can preprocess information:

  • leftMin[j] = smallest value to the left of j
  • rightMin[j] = smallest value to the right of j

Then for each position j, we simply check:

  • Is there a left value smaller than nums[j]?
  • Is there a right value smaller than nums[j]?

If both exist, we can compute:

$$leftMin[j] + nums[j] + rightMin[j]$$

This reduces the problem to linear time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(1) Checks every possible triplet
Optimal O(n) O(n) Precomputes minimum values on both sides

Algorithm Walkthrough

  1. Create an array leftMin of size n.

For every index j, leftMin[j] stores the minimum value seen before index j.

We scan from left to right while maintaining the smallest value encountered so far. 2. Create an array rightMin of size n.

For every index j, rightMin[j] stores the minimum value seen after index j.

We scan from right to left while maintaining the smallest value encountered so far. 3. Initialize the answer as infinity.

This allows us to keep track of the minimum valid mountain sum found so far. 4. Iterate through every possible middle index j.

For each j, check whether:

  • leftMin[j] < nums[j]
  • rightMin[j] < nums[j]

These conditions guarantee a valid mountain triplet exists with j as the peak. 5. If both conditions are true, compute the triplet sum.

$$leftMin[j] + nums[j] + rightMin[j]$$

Update the global minimum if this sum is smaller. 6. After processing all indices, return the answer.

If no valid triplet was found, return -1.

Why it works

For every possible peak position j, the algorithm selects the smallest valid left element and the smallest valid right element. Any larger choice would only increase the sum. Since every index is considered as a potential peak, and the optimal partners are chosen for each peak, the algorithm is guaranteed to find the minimum possible mountain triplet sum.

Python Solution

from typing import List

class Solution:
    def minimumSum(self, nums: List[int]) -> int:
        n = len(nums)

        left_min = [0] * n
        right_min = [0] * n

        current_min = float('inf')

        for i in range(n):
            left_min[i] = current_min
            current_min = min(current_min, nums[i])

        current_min = float('inf')

        for i in range(n - 1, -1, -1):
            right_min[i] = current_min
            current_min = min(current_min, nums[i])

        answer = float('inf')

        for j in range(n):
            if left_min[j] < nums[j] and right_min[j] < nums[j]:
                triplet_sum = left_min[j] + nums[j] + right_min[j]
                answer = min(answer, triplet_sum)

        return answer if answer != float('inf') else -1

The implementation begins by allocating two arrays, left_min and right_min. These arrays store the smallest values seen on the left and right sides of every index.

The first loop scans from left to right. Before updating the running minimum, the current minimum value is stored into left_min[i]. This ensures that left_min[i] only contains elements strictly before index i.

The second loop performs the same logic in reverse order. right_min[i] stores the minimum element strictly after index i.

After preprocessing, the final loop evaluates every index as a possible mountain peak. If both neighboring minimums are strictly smaller than the current value, a valid mountain exists. The sum is computed and used to update the answer.

Finally, if the answer was never updated, the function returns -1.

Go Solution

package main

import "math"

func minimumSum(nums []int) int {
	n := len(nums)

	leftMin := make([]int, n)
	rightMin := make([]int, n)

	currentMin := math.MaxInt

	for i := 0; i < n; i++ {
		leftMin[i] = currentMin

		if nums[i] < currentMin {
			currentMin = nums[i]
		}
	}

	currentMin = math.MaxInt

	for i := n - 1; i >= 0; i-- {
		rightMin[i] = currentMin

		if nums[i] < currentMin {
			currentMin = nums[i]
		}
	}

	answer := math.MaxInt

	for j := 0; j < n; j++ {
		if leftMin[j] < nums[j] && rightMin[j] < nums[j] {
			sum := leftMin[j] + nums[j] + rightMin[j]

			if sum < answer {
				answer = sum
			}
		}
	}

	if answer == math.MaxInt {
		return -1
	}

	return answer
}

The Go implementation follows exactly the same logic as the Python version. Since Go does not have a built-in infinity constant for integers, math.MaxInt is used as a sentinel value.

Slices are used for the preprocessing arrays, and integer comparisons are performed directly. Since the maximum possible sum is well within 64-bit integer limits, standard Go integers are sufficient.

Worked Examples

Example 1

nums = [8,6,1,5,3]

Step 1: Build left_min

Index nums[i] left_min[i] Running Minimum After Update
0 8 inf 8
1 6 8 6
2 1 6 1
3 5 1 1
4 3 1 1

Result:

left_min = [inf, 8, 6, 1, 1]

Step 2: Build right_min

Index nums[i] right_min[i] Running Minimum After Update
4 3 inf 3
3 5 3 3
2 1 3 1
1 6 1 1
0 8 1 1

Result:

right_min = [1, 1, 3, 3, inf]

Step 3: Evaluate Peaks

j nums[j] left_min[j] right_min[j] Valid? Sum
0 8 inf 1 No -
1 6 8 1 No -
2 1 6 3 No -
3 5 1 3 Yes 9
4 3 1 inf No -

Minimum sum is 9.

Example 2

nums = [5,4,8,7,10,2]

left_min

[inf, 5, 4, 4, 4, 4]

right_min

[2, 2, 2, 2, 2, inf]

Peak Evaluation

j nums[j] Valid? Sum
0 5 No -
1 4 No -
2 8 Yes 14
3 7 Yes 13
4 10 Yes 16
5 2 No -

Minimum sum is 13.

Example 3

nums = [6,5,4,3,4,5]

No index has both a smaller left value and a smaller right value simultaneously.

Therefore, no valid mountain exists, and the answer is -1.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Three linear scans through the array
Space O(n) Two auxiliary arrays of size n

The algorithm performs one left-to-right traversal, one right-to-left traversal, and one final validation traversal. Since each pass is linear, the total runtime remains O(n).

The extra memory usage comes from storing the left_min and right_min arrays, each of which requires O(n) space.

Test Cases

from typing import List

class Solution:
    def minimumSum(self, nums: List[int]) -> int:
        n = len(nums)

        left_min = [0] * n
        right_min = [0] * n

        current_min = float('inf')

        for i in range(n):
            left_min[i] = current_min
            current_min = min(current_min, nums[i])

        current_min = float('inf')

        for i in range(n - 1, -1, -1):
            right_min[i] = current_min
            current_min = min(current_min, nums[i])

        answer = float('inf')

        for j in range(n):
            if left_min[j] < nums[j] and right_min[j] < nums[j]:
                answer = min(
                    answer,
                    left_min[j] + nums[j] + right_min[j]
                )

        return answer if answer != float('inf') else -1

sol = Solution()

assert sol.minimumSum([8,6,1,5,3]) == 9       # provided example 1
assert sol.minimumSum([5,4,8,7,10,2]) == 13   # provided example 2
assert sol.minimumSum([6,5,4,3,4,5]) == -1    # provided example 3

assert sol.minimumSum([1,3,2]) == 6           # smallest valid array
assert sol.minimumSum([1,2,3]) == -1          # strictly increasing
assert sol.minimumSum([3,2,1]) == -1          # strictly decreasing

assert sol.minimumSum([2,1,2]) == -1          # peak cannot be at edges
assert sol.minimumSum([1,5,1]) == 7           # simple valid mountain

assert sol.minimumSum([10,1,9,2,8,3]) == 12  # multiple possible peaks
assert sol.minimumSum([1,1,1,1]) == -1       # duplicates fail strict inequality

assert sol.minimumSum([100000000,1,99999999]) == -1  # large values
assert sol.minimumSum([4,9,1,3,2]) == 6      # optimal peak not largest element
Test Why
[8,6,1,5,3] Validates provided example
[5,4,8,7,10,2] Tests multiple valid peaks
[6,5,4,3,4,5] Verifies no mountain exists
[1,3,2] Smallest possible valid case
[1,2,3] Strictly increasing array
[3,2,1] Strictly decreasing array
[2,1,2] Peak cannot be at array boundary
[1,5,1] Simple symmetric mountain
[10,1,9,2,8,3] Multiple candidate triplets
[1,1,1,1] Duplicate values with strict inequality
[100000000,1,99999999] Large integer values
[4,9,1,3,2] Best answer uses nontrivial peak

Edge Cases

One important edge case occurs when the array is strictly increasing or strictly decreasing. In these situations, no element can have both a smaller left neighbor and a smaller right neighbor. A naive implementation might accidentally accept invalid configurations if it only checks one side. The current implementation explicitly verifies both conditions before computing a sum.

Another important edge case involves duplicate values. The problem requires strict inequalities, meaning equal values are not valid. For example, [1,1,1] cannot form a mountain. The implementation correctly handles this by using the < operator instead of <=.

A third edge case occurs when the smallest element appears in the middle of the array. Since the peak must be strictly larger than both side elements, such positions can never form valid mountains. The algorithm naturally filters these out because neither side minimum will be smaller than the middle value.

A final subtle edge case involves very large numbers. Since values can be as large as 10^8, the sum of three values can exceed 32-bit signed integer limits in some languages. Python handles large integers automatically, while Go uses standard integers that safely support the required range on modern systems.