LeetCode 2908 - Minimum Sum of Mountain Triplets I

The problem asks us to find the minimum possible sum of a "mountain triplet" within a given array of integers. A mountain triplet is defined as three indices (i, j, k) such that i < j < k, nums[i] < nums[j], and nums[k] < nums[j].

leetcodeeasyarray

LeetCode Problem 2908

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

The problem asks us to find the minimum possible sum of a "mountain triplet" within a given array of integers. A mountain triplet is defined as three indices (i, j, k) such that i < j < k, nums[i] < nums[j], and nums[k] < nums[j]. Essentially, the middle element must be strictly larger than both its left and right neighbors, forming a peak. The input is an array of integers, with a length between 3 and 50, and integer values between 1 and 50. The expected output is either the minimum sum of a valid mountain triplet or -1 if no mountain exists.

Given the small constraints (nums.length <= 50), the problem is manageable without highly complex data structures. Edge cases include arrays that are strictly increasing or decreasing, arrays where all elements are equal, and arrays with multiple potential mountains where the minimal sum is non-obvious.

Approaches

Brute Force

A brute-force approach would involve iterating over all possible triplets (i, j, k) where i < j < k, checking whether they form a mountain, and keeping track of the minimum sum. This approach works because it explicitly considers every triplet, ensuring correctness. However, the number of triplets is combinatorial, specifically O(n^3), which is feasible for n = 50 but not efficient.

Optimal Approach

The key observation is that for each potential peak nums[j], we only need the smallest value to its left that is smaller than nums[j] and the smallest value to its right that is smaller than nums[j]. By iterating over the array and maintaining these minimums, we reduce the complexity from O(n^3) to O(n^2). For each index j, we scan all previous indices i < j to find a valid left candidate and all following indices k > j to find a valid right candidate, then compute the sum if both exist. This guarantees the minimal sum is captured.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(1) Check every triplet (i, j, k) for the mountain property
Optimal O(n^2) O(1) For each peak j, find smallest valid left and right values

Algorithm Walkthrough

  1. Initialize a variable min_sum to inf. This will store the minimum sum of a valid mountain triplet.
  2. Iterate over each index j from 1 to len(nums)-2, treating nums[j] as the potential peak.
  3. For each j, initialize left_min to inf. Scan all indices i to the left of j (0 <= i < j). If nums[i] < nums[j], update left_min if nums[i] is smaller than the current left_min.
  4. Similarly, initialize right_min to inf. Scan all indices k to the right of j (j < k < n). If nums[k] < nums[j], update right_min if nums[k] is smaller than the current right_min.
  5. If both left_min and right_min are not inf, compute the sum left_min + nums[j] + right_min and update min_sum if this sum is smaller than the current min_sum.
  6. After iterating all potential peaks, return min_sum if it has been updated, otherwise return -1 if no mountain exists.

Why it works: For each peak candidate, we only need the minimal smaller numbers on both sides. By considering every potential peak, we guarantee that the absolute minimum sum is found.

Python Solution

from typing import List

class Solution:
    def minimumSum(self, nums: List[int]) -> int:
        n = len(nums)
        min_sum = float('inf')
        
        for j in range(1, n - 1):
            left_min = float('inf')
            right_min = float('inf')
            
            for i in range(j):
                if nums[i] < nums[j]:
                    left_min = min(left_min, nums[i])
            
            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

The implementation follows the algorithm exactly. The outer loop selects the peak, and the two inner loops find the smallest valid left and right elements. The conditional ensures we only compute sums for valid mountains. If no valid mountain exists, min_sum remains inf, and we return -1.

Go Solution

import "math"

func minimumSum(nums []int) int {
    n := len(nums)
    minSum := math.MaxInt32
    
    for j := 1; j < n-1; j++ {
        leftMin := math.MaxInt32
        rightMin := math.MaxInt32
        
        for i := 0; i < j; i++ {
            if nums[i] < nums[j] && nums[i] < leftMin {
                leftMin = nums[i]
            }
        }
        
        for k := j + 1; k < n; k++ {
            if nums[k] < nums[j] && nums[k] < rightMin {
                rightMin = nums[k]
            }
        }
        
        if leftMin != math.MaxInt32 && rightMin != math.MaxInt32 {
            sum := leftMin + nums[j] + rightMin
            if sum < minSum {
                minSum = sum
            }
        }
    }
    
    if minSum == math.MaxInt32 {
        return -1
    }
    return minSum
}

Go differences: Instead of float('inf'), we use math.MaxInt32. Go arrays are slices, so we iterate with standard index ranges. Overflow is not a concern because the maximum possible sum is 50 + 50 + 50 = 150, well below int32 limits.

Worked Examples

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

  • j = 1 (6): left < 6 → 8 (not valid), right < 6 → 1, 5, 3 → min 1, sum = 6 + 1 + 1? invalid, left not valid
  • j = 2 (1): left < 1 → none, skip
  • j = 3 (5): left < 5 → 1, right < 5 → 3, sum = 1 + 5 + 3 = 9 → update min_sum = 9
  • j = 4 (3): left < 3 → 1, right < 3 → none, skip

Return 9.

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

  • j = 2 (8): left < 8 → 5,4 → min 4, right < 8 → 7,10,2 → min 2, sum = 4+8+2=14
  • j = 3 (7): left < 7 → 5,4 → min 4, right < 7 → 2 → sum = 4+7+2=13 → update min_sum
  • j = 4 (10): left < 10 → 5,4,8,7 → min 4, right < 10 → 2 → sum = 4+10+2=16
  • Return 13

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

  • Scan all j: no valid mountain triplets found → return -1

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) Two nested loops for each peak j over the left and right sides
Space O(1) Only constant extra variables are used

The algorithm scans the array repeatedly for each potential peak, but since n <= 50, O(n^2) is efficient. No extra data structures are required, keeping space minimal.

Test Cases

# Provided examples
assert Solution().minimumSum([8,6,1,5,3]) == 9
assert Solution().minimumSum([5,4,8,7,10,2]) == 13
assert Solution().minimumSum([6,5,4,3,4,5]) == -1

# Edge cases
assert Solution().minimumSum([1,2,3]) == -1 # strictly increasing, no mountain
assert Solution().minimumSum([3,2,1]) == -1 # strictly decreasing, no mountain
assert Solution().minimumSum([1,3,2]) == 6  # single mountain
assert Solution().minimumSum([50,1,50]) == 101 # peak in middle
assert Solution().minimumSum([1,50,1,2,49,2]) == 4+50+1 # multiple options, minimal sum chosen

| Test | Why |