Leetcode Problem 2909. Minimum Sum of Mountain Triplets II

2909. Minimum Sum of Mountain Triplets II

Leetcode Solutions

Dynamic Programming with Left and Right Minimums

  1. Initialize two arrays, minLeft and minRight, of the same length as nums.
  2. Fill minLeft such that minLeft[i] contains the minimum value in nums to the left of index i.
  3. Fill minRight such that minRight[i] contains the minimum value in nums to the right of index i.
  4. Initialize a variable minSum to track the minimum sum of a mountain triplet, and set it to a very large value initially.
  5. Iterate through the nums array from the second element to the second-to-last element.
  6. For each element nums[i], check if it is greater than both minLeft[i] and minRight[i].
  7. If it is, calculate the sum of the triplet (nums[i] + minLeft[i] + minRight[i]) and update minSum if this sum is smaller.
  8. After the iteration, check if minSum was updated. If it was not, return -1 to indicate no mountain triplet was found. Otherwise, return minSum.
UML Thumbnail

Brute Force Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...