Minimum Sum of Mountain Triplets I - Video Solutions

Problem Overview: You are given an integer array nums. A valid mountain triplet (i, j, k) must satisfy i < j < k and nums[i] < nums[j] and nums[k] < nums[j]. The goal is to find the minimum possible sum nums[i] + nums[j] + nums[k]. If no such triplet exists, return -1. The challenge is efficiently identifying a middle peak while ensuring smaller values exist on both sides.

Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)

The direct solution checks every possible triplet. Use three nested loops to iterate over indices i, j, and k such that i < j < k. For each combination, verify the mountain condition nums[i] < nums[j] and nums[k] < nums[j]. If valid, compute the sum and track the minimum. This approach works because it exhaustively explores the search space, but the O(n^3) time complexity becomes impractical as the array grows. Still useful as a baseline or when explaining the problem during interviews to demonstrate understanding before optimizing. The algorithm operates directly on the array with no additional data structures.

Approach 2: Optimized Two-Pass with Prefix and Suffix Minimums (O(n) time, O(n) space)

The key observation: for a fixed middle index j, you only need the smallest value on the left that is less than nums[j] and the smallest value on the right that is also less than nums[j]. Instead of searching every time, precompute this information.

First pass: build a prefix array where leftMin[j] stores the minimum value seen before index j. Second pass from right to left: maintain a running suffix minimum representing the smallest value to the right. For each index j, check whether both sides contain values smaller than nums[j]. If they do, compute the candidate sum leftMin[j] + nums[j] + rightMin and update the global minimum.

This turns the triple search into two linear scans. Each index is processed a constant number of times, giving O(n) time complexity with O(n) auxiliary space for prefix tracking. The technique relies on maintaining running minimums, a common pattern in array problems and prefix-style preprocessing similar to prefix-based techniques.

Recommended for interviews: Interviewers expect the two-pass optimized solution. Starting with brute force shows you understand the mountain constraint and index ordering. Transitioning to the prefix/suffix minimum idea demonstrates pattern recognition and the ability to reduce O(n^3) enumeration to an O(n) scan, which is the key skill being evaluated.