Minimum Sum of Mountain Triplets II - Video Solutions

Problem Overview: You are given an integer array and must find a triplet (i, j, k) such that i < j < k, nums[i] < nums[j], and nums[k] < nums[j]. The element at index j acts as the mountain peak. Among all valid mountain triplets, return the minimum possible value of nums[i] + nums[j] + nums[k]. If no valid triplet exists, return -1. The challenge is efficiently identifying smaller elements on both sides of every potential peak.

Approach 1: Peak and Two-Pointer Strategy (O(n²) time, O(1) space)

Treat every index j as the potential mountain peak. For each peak, scan the left side to find the smallest value nums[i] where i < j and nums[i] < nums[j]. Then scan the right side to find the smallest value nums[k] where k > j and nums[k] < nums[j]. If both exist, compute the sum and track the minimum across all peaks. This approach relies only on direct iteration and works well for understanding the constraint structure of the problem. However, repeatedly scanning both sides for every peak leads to quadratic time complexity. You mainly use basic array traversal with pointer movement similar to manual two‑pointer exploration.

Approach 2: Optimized Precomputation Method (O(n) time, O(n) space)

The key observation: for every potential peak j, you only need the smallest valid value on the left and the smallest valid value on the right. Precompute a prefix minimum array where leftMin[j] stores the smallest element seen before index j. Similarly compute a suffix minimum array where rightMin[j] stores the smallest element to the right of j. Then iterate through the array once and treat each index as the peak. A valid mountain exists only if leftMin[j] < nums[j] and rightMin[j] < nums[j]. When both conditions hold, calculate leftMin[j] + nums[j] + rightMin[j] and update the global minimum.

This preprocessing removes repeated scanning. Each element is processed a constant number of times: once during prefix computation, once during suffix computation, and once during the peak evaluation pass. The result is linear time complexity with predictable memory usage, making it the most practical approach for large arrays.

Recommended for interviews: The optimized precomputation method is the expected solution. Interviewers want to see that you convert repeated searches into prefix/suffix preprocessing, a common pattern in array problems. Mentioning the naive scanning approach first shows you understand the problem structure, while implementing the O(n) optimization demonstrates strong algorithmic thinking.