Minimum Sum of Mountain Triplets I — LeetCode 2908 Python Solution
EasyArray
- Problem
- #2908
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given a 0-indexed array nums of integers. A triplet of indices (i, j, k) is a mountain if: i < j < k nums[i] < nums[j] and nums[k] < nums[j] Return the minimum possible sum of a mountain triplet of nums.
Example
- Input
- nums = [8,6,1,5,3]
- Output
- 9
- Explanation
- Triplet (2, 3, 4) is a mountain triplet of sum 9 since:
Python solution
Python
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 ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Related problems
Frequently asked questions
- How hard is LeetCode 2908. Minimum Sum of Mountain Triplets I?
- LeetCode 2908. Minimum Sum of Mountain Triplets I is rated Easy on LeetCode.
- What is the time complexity of LeetCode 2908. Minimum Sum of Mountain Triplets I?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 2908. Minimum Sum of Mountain Triplets I?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2908. Minimum Sum of Mountain Triplets I cover?
- LeetCode 2908. Minimum Sum of Mountain Triplets I is tagged Array on LeetCode.