Minimum Sum of Mountain Triplets II
MedPrompt
You are given a 0-indexed array nums of integers.
A triplet of indices (i, j, k) is a mountain if:
i < j < knums[i] < nums[j]andnums[k] < nums[j]
Return the minimum possible sum of a mountain triplet of nums. If no such triplet exists, return -1.
Example 1:
Input: nums = [8,6,1,5,3]
Output: 9
Explanation: Triplet (2, 3, 4) is a mountain triplet of sum 9 since:
- 2 < 3 < 4
- nums[2] < nums[3] and nums[4] < nums[3]
And the sum of this triplet is nums[2] + nums[3] + nums[4] = 9. It can be shown that there are no mountain triplets with a sum of less than 9.Example 2:
Input: nums = [5,4,8,7,10,2]
Output: 13
Explanation: Triplet (1, 3, 5) is a mountain triplet of sum 13 since:
- 1 < 3 < 5
- nums[1] < nums[3] and nums[5] < nums[3]
And the sum of this triplet is nums[1] + nums[3] + nums[5] = 13. It can be shown that there are no mountain triplets with a sum of less than 13.Example 3:
Input: nums = [6,5,4,3,4,5]
Output: -1
Explanation: It can be shown that there are no mountain triplets in nums.
Constraints:
3 <= nums.length <= 1051 <= nums[i] <= 108
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves checking every possible triplet of indices (i, j, k) to see if it forms a mountain triplet. It's the most straightforward but also the least efficient method, serving as a baseline.
Algorithm
- Initialize
minSumto a very large value (e.g.,Long.MAX_VALUE). - Use a first loop to iterate through index
ifrom0ton-3. - Inside, use a second loop to iterate through index
jfromi+1ton-2. - Inside the second loop, use a third loop to iterate through index
kfromj+1ton-1. - In the innermost loop, check if the triplet
(i, j, k)forms a mountain:nums[i] < nums[j]andnums[k] < nums[j]. - If it is a mountain, calculate the sum
nums[i] + nums[j] + nums[k]and updateminSumwith the minimum value seen so far. - After all loops complete, if
minSumremains at its initial large value, no mountain triplet was found, so return -1. - Otherwise, return the
minSum.
Walkthrough
We use three nested loops to generate all combinations of i, j, and k such that 0 <= i < j < k < n, where n is the length of the array. For each triplet, we check if it satisfies the mountain conditions: nums[i] < nums[j] and nums[k] < nums[j]. If the conditions are met, we calculate the sum nums[i] + nums[j] + nums[k]. We keep track of the minimum sum found so far. If after checking all triplets, no mountain triplet has been found, we return -1. Otherwise, we return the minimum sum.
class Solution { public int minimumSum(int[] nums) { int n = nums.length; long minSum = Long.MAX_VALUE; boolean found = false; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { if (nums[i] < nums[j] && nums[k] < nums[j]) { minSum = Math.min(minSum, (long)nums[i] + nums[j] + nums[k]); found = true; } } } } return found ? (int)minSum : -1; }}Complexity
Time
O(n³), where n is the number of elements in `nums`. The three nested loops lead to a cubic time complexity, which is too slow for the problem's constraints (`n <= 10^5`).
Space
O(1), as we only use a few variables to store the minimum sum and loop indices.
Trade-offs
Pros
Simple to understand and implement.
Correct for small input sizes.
Cons
Extremely inefficient due to its cubic time complexity.
Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
Instead of three nested loops, we can improve the logic by fixing the middle element nums[j] (the peak of the mountain) and then searching for the best possible left (nums[i]) and right (nums[k]) elements for it. This reduces the complexity from cubic to quadratic.
Algorithm
- Initialize
minSumto a very large value. - Iterate through the array with an index
jfrom1ton-2, consideringnums[j]as the peak of a potential mountain. - For each
j, initializeminLeftandminRightto a large value. - In a nested loop, iterate
ifrom0toj-1. Ifnums[i] < nums[j], updateminLeft = Math.min(minLeft, nums[i]). - In another nested loop, iterate
kfromj+1ton-1. Ifnums[k] < nums[j], updateminRight = Math.min(minRight, nums[k]). - If both a valid
minLeftandminRightwere found, calculate the summinLeft + nums[j] + minRightand update the overallminSum. - After the main loop, if
minSumis unchanged, return -1. Otherwise, returnminSum.
Walkthrough
We iterate through the array with a main loop for index j from 1 to n-2. For each nums[j], we treat it as a potential peak. Then, we perform two separate searches: one to its left and one to its right. We search the subarray nums[0...j-1] for the minimum element that is less than nums[j]. We do the same for the subarray nums[j+1...n-1]. If we find such minimums on both sides, we form a triplet and update our global minimum sum. This avoids the third nested loop of the pure brute-force approach.
class Solution { public int minimumSum(int[] nums) { int n = nums.length; long minSum = Long.MAX_VALUE; for (int j = 1; j < n - 1; j++) { int minLeft = Integer.MAX_VALUE; int minRight = Integer.MAX_VALUE; // Find minimum on the left for (int i = 0; i < j; i++) { if (nums[i] < nums[j]) { minLeft = Math.min(minLeft, nums[i]); } } // Find minimum on the right if (minLeft != Integer.MAX_VALUE) { for (int k = j + 1; k < n; k++) { if (nums[k] < nums[j]) { minRight = Math.min(minRight, nums[k]); } } } if (minLeft != Integer.MAX_VALUE && minRight != Integer.MAX_VALUE) { minSum = Math.min(minSum, (long)minLeft + nums[j] + minRight); } } return minSum == Long.MAX_VALUE ? -1 : (int)minSum; }}Complexity
Time
O(n²), where n is the number of elements. The main loop runs O(n) times, and inside it, the two searches take O(j) and O(n-j) time, leading to an overall quadratic complexity.
Space
O(1), as we only use a constant amount of extra space for variables.
Trade-offs
Pros
More efficient than the O(n³) brute-force approach.
Maintains a simple structure with constant extra space.
Cons
Still inefficient for large inputs and will likely time out.
Performs redundant computations by repeatedly scanning the left and right subarrays for each potential peak.
The O(n²) approach is slow because finding the minimums to the left and right of each element j is done repeatedly. We can optimize this to a linear time solution by precomputing these minimums. This allows us to find the minimum sum in a single pass over the potential peaks.
Algorithm
- If array length
n < 3, return -1. - Create a
prefixMinarray of sizen.prefixMin[i]will store the minimum value innums[0...i]. Populate it by iterating from left to right. - Create a
suffixMinarray of sizen.suffixMin[i]will store the minimum value innums[i...n-1]. Populate it by iterating from right to left. - Initialize
minSumto a very large value. - Iterate with index
jfrom1ton-2. - For each
j, the minimum element to its left isprefixMin[j-1]and to its right issuffixMin[j+1]. - Check if
prefixMin[j-1] < nums[j]andsuffixMin[j+1] < nums[j]. - If the condition is true, calculate the sum
prefixMin[j-1] + nums[j] + suffixMin[j+1]and updateminSum. - After the loop, if
minSumis unchanged, return -1. Otherwise, returnminSum.
Walkthrough
The key insight is that for any potential peak nums[j], the best possible left element nums[i] will always be the minimum value in the entire prefix nums[0...j-1]. Similarly, the best right element nums[k] will be the minimum in the suffix nums[j+1...n-1]. We can precompute all prefix minimums and all suffix minimums in O(n) time.
First, we create a prefixMin array where prefixMin[i] stores min(nums[0]...nums[i]). Then, we create a suffixMin array where suffixMin[i] stores min(nums[i]...nums[n-1]). With these arrays, we can iterate through j from 1 to n-2. For each j, we can find the left and right minimums in O(1) time by looking up prefixMin[j-1] and suffixMin[j+1]. We check if they form a mountain with nums[j] and update the minimum sum accordingly.
class Solution { public int minimumSum(int[] nums) { int n = nums.length; if (n < 3) { return -1; } // prefixMin[i] = min(nums[0]...nums[i]) int[] prefixMin = new int[n]; prefixMin[0] = nums[0]; for (int i = 1; i < n; i++) { prefixMin[i] = Math.min(prefixMin[i - 1], nums[i]); } // suffixMin[i] = min(nums[i]...nums[n-1]) int[] suffixMin = new int[n]; suffixMin[n - 1] = nums[n - 1]; for (int i = n - 2; i >= 0; i--) { suffixMin[i] = Math.min(suffixMin[i + 1], nums[i]); } long minSum = Long.MAX_VALUE; for (int j = 1; j < n - 1; j++) { int leftMin = prefixMin[j - 1]; int rightMin = suffixMin[j + 1]; if (leftMin < nums[j] && rightMin < nums[j]) { minSum = Math.min(minSum, (long)leftMin + nums[j] + rightMin); } } return minSum == Long.MAX_VALUE ? -1 : (int)minSum; }}Complexity
Time
O(n). We make three separate passes through the array: one to compute `prefixMin`, one for `suffixMin`, and one to find the minimum sum. Each pass takes O(n) time, making the total O(n).
Space
O(n), as we use two additional arrays, `prefixMin` and `suffixMin`, each of size `n`.
Trade-offs
Pros
Highly efficient with an optimal time complexity.
Guaranteed to pass within the time limits for the given constraints.
Cons
Uses extra space proportional to the input size for the precomputed arrays.
Solutions
Solution
class Solution {public int minimumSum(int[] nums) { int n = nums.length; int[] right = new int[n + 1]; final int inf = 1 << 30; right[n] = inf; for (int i = n - 1; i >= 0; --i) { right[i] = Math.min(right[i + 1], nums[i]); } int ans = inf, left = inf; for (int i = 0; i < n; ++i) { if (left < nums[i] && right[i + 1] < nums[i]) { ans = Math.min(ans, left + nums[i] + right[i + 1]); } left = Math.min(left, nums[i]); } return ans == inf ? -1 : ans; }}class Solution {public: int minimumSum(vector<int> &nums) { int n = nums.size(); const int inf = 1 << 30; int right[n + 1]; right[n] = inf; for (int i = n - 1; ~i; --i) { right[i] = min(right[i + 1], nums[i]); } int ans = inf, left = inf; for (int i = 0; i < n; ++i) { if (left < nums[i] && right[i + 1] < nums[i]) { ans = min(ans, left + nums[i] + right[i + 1]); } left = min(left, nums[i]); } return ans == inf ? -1 : ans; }};class Solution: def minimumSum(self, nums: List[int]) -> int: n = len(nums) right = [inf] * (n + 1) for i in range(n - 1, - 1, - 1): right[i] = min(right[i + 1], nums[i]) 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) return - 1 if ans == inf else ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.