Leetcode 2909: Minimum Sum of Mountain Triplets II
You are given an array of integers called nums. A mountain triplet consists of three indices (i, j, k) such that i < j < k, nums[i] < nums[j], and nums[k] < nums[j]. Your task is to return the minimum possible sum of any such mountain triplet. If no such triplet exists, return -1.
Problem
Approach
Steps
Complexity
Input: You are given an integer array nums of length n.
Example: nums = [12, 7, 8, 15, 5]
Constraints:
• 3 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^8
Output: Return the minimum sum of a valid mountain triplet (i, j, k), or -1 if no such triplet exists.
Example: For the input [12, 7, 8, 15, 5], the output should be 22.
Constraints:
Goal: The goal is to identify the minimum sum of a valid mountain triplet in the array.
Steps:
• Create an array to store the smallest number to the right of each element.
• Iterate through the array and for each number, check if there is a smaller element on its left and right.
• Track the minimum sum of such valid mountain triplets.
• Return the minimum sum if any valid triplet is found, otherwise return -1.
Goal: The array size and values are within manageable limits for a solution that processes elements sequentially.
Steps:
• 3 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^8
Assumptions:
• The input will always have at least three numbers.
• The solution should work for all values within the given constraints.
• Input: nums = [12, 7, 8, 15, 5]
• Explanation: In this case, the mountain triplet (1, 2, 4) is valid because 7 < 8 and 5 < 8. The sum of this triplet is 7 + 8 + 5 = 22, which is the minimum sum.
Approach: The approach involves using a preprocessing step to determine the smallest elements on the right for each element, and then finding the minimum sum of valid mountain triplets.
Observations:
• We need to efficiently check for each element if there exists a valid mountain triplet using two conditions: a smaller element to its left and a smaller element to its right.
• We can optimize this problem using a linear pass to find the smallest right elements, and then another pass to find valid triplets.
Steps:
• First, create a new array to store the smallest element to the right of each index in the array.
• Then, iterate through the array from left to right to check if each element can form a valid mountain triplet with its left and right neighbors.
• Track the minimum sum of valid mountain triplets and return it, or return -1 if no valid triplet is found.
Empty Inputs:
• The input array will always have at least three elements.
Large Inputs:
• The solution should be efficient enough to handle the upper constraint of nums.length up to 10^5.
Special Values:
• Consider arrays where no valid mountain triplets exist, such as arrays with strictly increasing or decreasing numbers.
Constraints:
• All values of nums will be between 1 and 10^8.
int minimumSum(vector<int>& nums) {
vector<int> smallestRight(nums.size(), nums.back());
for(int i = nums.size()-2; i >= 0; i--){
smallestRight[i] = min(smallestRight[i+1], nums[i]);
}
int smallestLeft = nums[0], ans = -1;
for(int i = 1; i < nums.size(); i++){
if(smallestLeft < nums[i] && smallestRight[i] < nums[i]){
if(ans == -1) ans = nums[i] + smallestRight[i] + smallestLeft;
else ans = min(ans, nums[i] + smallestRight[i] + smallestLeft);
}
smallestLeft = min(smallestLeft, nums[i]);
}
return ans;
}
1 : Function Definition
int minimumSum(vector<int>& nums) {
Defines the `minimumSum` function, which takes a vector of integers `nums` and returns the minimum sum of a valid triplet satisfying certain conditions.
2 : Array Initialization
vector<int> smallestRight(nums.size(), nums.back());
Initializes the `smallestRight` array, which will store the smallest value to the right of each element in `nums`. It starts with the last element of `nums`.
3 : Loop: Backward Traversal
for(int i = nums.size()-2; i >= 0; i--){
Starts a loop that traverses the array `nums` from right to left (excluding the last element) to populate the `smallestRight` array.
4 : Updating Smallest Right Value
smallestRight[i] = min(smallestRight[i+1], nums[i]);
For each element, updates `smallestRight[i]` to store the minimum of `smallestRight[i+1]` and `nums[i]`, which ensures it holds the smallest value to the right of `nums[i]`.
5 : Variable Initialization
int smallestLeft = nums[0], ans = -1;
Initializes `smallestLeft` with the first element of `nums`, and `ans` to `-1` to represent that no valid triplet has been found yet.
6 : Loop: Forward Traversal
for(int i = 1; i < nums.size(); i++){
Starts a loop that traverses the array `nums` from left to right (excluding the first element).
7 : Conditional Check: Triplet Validation
if(smallestLeft < nums[i] && smallestRight[i] < nums[i]){
Checks if the current element `nums[i]` forms a valid triplet with the elements to the left and right by ensuring that `smallestLeft < nums[i]` and `smallestRight[i] < nums[i]`.
8 : Condition Met: Update Answer
if(ans == -1) ans = nums[i] + smallestRight[i] + smallestLeft;
If `ans` is still `-1`, this is the first valid triplet found, so it updates `ans` with the sum of the triplet.
9 : Condition Met: Update Answer (Min)
else ans = min(ans, nums[i] + smallestRight[i] + smallestLeft);
If a valid triplet is found and `ans` is not `-1`, it updates `ans` with the minimum sum of the current triplet and the previous smallest sum.
10 : Updating Smallest Left Value
smallestLeft = min(smallestLeft, nums[i]);
Updates `smallestLeft` to the minimum of its current value and `nums[i]` to ensure it always holds the smallest value to the left of `nums[i]`.
11 : Return Statement
return ans;
Returns the minimum sum found from the valid triplet, or `-1` if no valid triplet exists.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) because we only perform two passes over the array.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the additional array used to store the smallest elements to the right of each index.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus