Minimum Sum of Mountain Triplets I
EasyPrompt
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 <= 501 <= nums[i] <= 50
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the problem definition into code. It involves using three nested loops to iterate through all possible triplets of indices (i, j, k) such that i < j < k. For each triplet, it checks if it satisfies the mountain condition (nums[i] < nums[j] and nums[k] < nums[j]). If it does, the sum of the triplet's values is calculated and compared with the minimum sum found so far.
Algorithm
-
- Initialize a variable
minSumto a very large value (e.g.,Integer.MAX_VALUE) and a boolean flagfoundtofalse.
- Initialize a variable
-
- Use a loop to iterate through each possible index
ifrom0ton-3.
- Use a loop to iterate through each possible index
-
- Inside this loop, nest another loop to iterate through each possible index
jfromi+1ton-2.
- Inside this loop, nest another loop to iterate through each possible index
-
- Inside the second loop, nest a third loop to iterate through each possible index
kfromj+1ton-1.
- Inside the second loop, nest a third loop to iterate through each possible index
-
- For each triplet of indices
(i, j, k), check if it forms a mountain:nums[i] < nums[j]andnums[k] < nums[j].
- For each triplet of indices
-
- If the condition is true, calculate the sum
currentSum = nums[i] + nums[j] + nums[k].
- If the condition is true, calculate the sum
-
- Update
minSum = Math.min(minSum, currentSum)and setfoundtotrue.
- Update
-
- After all loops complete, if
foundistrue, returnminSum. Otherwise, return -1.
- After all loops complete, if
Walkthrough
The brute-force method is the most straightforward way to solve the problem. We systematically check every possible combination of three distinct indices i, j, and k that satisfy the i < j < k ordering.
We can achieve this with three nested loops. The outermost loop picks the first element nums[i], the middle loop picks the second element nums[j], and the innermost loop picks the third element nums[k]. Inside the innermost loop, we have a triplet and can check if it meets the mountain criteria. If it does, we compute its sum and update our minimum sum if the current sum is smaller. We use a variable, initialized to a very large number, to keep track of this minimum sum. If, after checking all triplets, this variable hasn't changed, it means no mountain triplet exists, and we should return -1.
class Solution { public int minimumSum(int[] nums) { int n = nums.length; int minSum = Integer.MAX_VALUE; boolean found = false; for (int i = 0; i < n - 2; i++) { for (int j = i + 1; j < n - 1; j++) { for (int k = j + 1; k < n; k++) { if (nums[i] < nums[j] && nums[k] < nums[j]) { minSum = Math.min(minSum, nums[i] + nums[j] + nums[k]); found = true; } } } } return found ? minSum : -1; }}Complexity
Time
O(n³), where n is the length of the `nums` array. The three nested loops lead to a cubic number of operations, as we check every possible triplet.
Space
O(1), as we only use a constant amount of extra space for variables like `minSum` and loop counters.
Trade-offs
Pros
Simple to understand and implement.
Directly follows the problem statement without complex logic.
Cons
Highly inefficient due to its O(n³) time complexity.
Will be too slow for larger input constraints, although it passes for the given constraints (n <= 50).
Instead of iterating through all three indices, we can optimize by iterating through the middle index j (the peak) and then finding the best possible i and k. For a fixed j, to minimize the sum nums[i] + nums[j] + nums[k], we need to find the smallest nums[i] to its left (where i < j and nums[i] < nums[j]) and the smallest nums[k] to its right (where k > j and nums[k] < nums[j]).
Algorithm
-
- Initialize
minSumtoInteger.MAX_VALUE.
- Initialize
-
- Iterate through each possible peak index
jfrom1ton-2.
- Iterate through each possible peak index
-
- For each
j, initializeminLeftandminRighttoInteger.MAX_VALUE.
- For each
-
- Find the minimum element to the left of
j: Iterateifrom0toj-1. Ifnums[i] < nums[j], updateminLeft = min(minLeft, nums[i]).
- Find the minimum element to the left of
-
- Find the minimum element to the right of
j: Iteratekfromj+1ton-1. Ifnums[k] < nums[j], updateminRight = min(minRight, nums[k]).
- Find the minimum element to the right of
-
- If both
minLeftandminRightwere updated (i.e., are notInteger.MAX_VALUE), it means a valid mountain can be formed withjas the peak.
- If both
-
- Calculate the sum
minLeft + nums[j] + minRightand updateminSum = min(minSum, ...).
- Calculate the sum
-
- After the main loop, if
minSumis stillInteger.MAX_VALUE, return -1. Otherwise, returnminSum.
- After the main loop, if
Walkthrough
This approach improves upon the brute-force method by changing the iteration strategy. We fix the middle element of the potential triplet, nums[j], which acts as the peak of the mountain. The index j can range from 1 to n-2.
For each j, our goal is to find an i < j and a k > j such that nums[i] and nums[k] are both smaller than nums[j], and their sum is minimized. This is achieved by finding the absolute minimum element to the left of j that is smaller than nums[j], and the absolute minimum element to the right of j that is also smaller than nums[j].
We can find these two minimums by performing two separate linear scans for each j: one from 0 to j-1 and another from j+1 to n-1. If we find valid minimums on both sides, we form a triplet, calculate its sum, and update the global minimum sum.
class Solution { public int minimumSum(int[] nums) { int n = nums.length; int minSum = Integer.MAX_VALUE; for (int j = 1; j < n - 1; j++) { int minLeft = Integer.MAX_VALUE; for (int i = 0; i < j; i++) { if (nums[i] < nums[j]) { minLeft = Math.min(minLeft, nums[i]); } } int minRight = 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, minLeft + nums[j] + minRight); } } return minSum == Integer.MAX_VALUE ? -1 : minSum; }}Complexity
Time
O(n²), where n is the length of the array. The main loop runs `n-2` times for `j`. Inside it, we perform two scans (one to the left, one to the right) that take O(j) and O(n-j) time respectively, leading to an overall O(n) work per `j`.
Space
O(1), as we only use a constant amount of extra space for variables.
Trade-offs
Pros
Significantly more efficient than the O(n³) brute-force approach.
Still relatively easy to reason about and implement.
Requires no extra space.
Cons
The repeated scanning for
minLeftandminRightfor eachjis redundant work.While better than O(n³), it's not the most optimal solution.
This is the most efficient approach. It builds upon the O(n²) idea but avoids the repeated scans by precomputing the minimum values. We can create two auxiliary arrays: prefixMin and suffixMin. prefixMin[i] stores the minimum value in nums[0...i], and suffixMin[i] stores the minimum value in nums[i...n-1]. After a one-time O(n) computation for these arrays, we can find the minimum left and right elements for any peak j in O(1) time.
Algorithm
-
- Create a
prefixMinarray of sizen. InitializeprefixMin[0] = nums[0].
- Create a
-
- Fill the
prefixMinarray by iterating fromi = 1ton-1, settingprefixMin[i] = min(prefixMin[i-1], nums[i]).
- Fill the
-
- Create a
suffixMinarray of sizen. InitializesuffixMin[n-1] = nums[n-1].
- Create a
-
- Fill the
suffixMinarray by iterating fromi = n-2down to0, settingsuffixMin[i] = min(suffixMin[i+1], nums[i]).
- Fill the
-
- Initialize
minSumtoInteger.MAX_VALUE.
- Initialize
-
- Iterate through the potential peak index
jfrom1ton-2.
- Iterate through the potential peak index
-
- For each
j, get the minimum element to its left asleftMin = prefixMin[j-1]and the minimum to its right asrightMin = suffixMin[j+1].
- For each
-
- Check if a mountain can be formed:
leftMin < nums[j]andrightMin < nums[j].
- Check if a mountain can be formed:
-
- If true, update
minSum = min(minSum, leftMin + nums[j] + rightMin).
- If true, update
-
- After the loop, if
minSumisInteger.MAX_VALUE, return -1. Otherwise, returnminSum.
- After the loop, if
Walkthrough
To achieve a linear time solution, we can eliminate the repetitive work done in the O(n²) approach. The bottleneck was finding the minimum element to the left and right of each potential peak j. This can be optimized by precomputing these values.
We use two auxiliary arrays:
prefixMin:prefixMin[i]will store the minimum value in the subarraynums[0...i]. This can be computed in a single pass from left to right.suffixMin:suffixMin[i]will store the minimum value in the subarraynums[i...n-1]. This can be computed in a single pass from right to left.
After these two arrays are populated, we can iterate through each potential peak j from 1 to n-2. For any j, the minimum element in nums[0...j-1] is simply prefixMin[j-1], and the minimum element in nums[j+1...n-1] is suffixMin[j+1]. We can access these in O(1) time. We then check if these minimums are less than nums[j] to form a mountain, and if so, update our global minimum sum.
class Solution { public int minimumSum(int[] nums) { int n = nums.length; if (n < 3) { return -1; } 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]); } 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]); } int minSum = Integer.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, leftMin + nums[j] + rightMin); } } return minSum == Integer.MAX_VALUE ? -1 : minSum; }}Complexity
Time
O(n), where n is the length of the array. We make three separate passes through the array (one for `prefixMin`, one for `suffixMin`, and one for the final calculation), each taking O(n) time. The total time is O(n) + O(n) + O(n) = O(n).
Space
O(n), for the `prefixMin` and `suffixMin` arrays, each of size `n`.
Trade-offs
Pros
Highly efficient with a linear time complexity, making it the optimal solution.
The logic is a clear optimization of the previous approach.
Cons
Requires extra space proportional to the input size for the precomputation 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.