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.
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; }}Video 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.