Skip to content

2909. Minimum Sum of Mountain Triplets II 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  // Same as 2908. Minimum Sum of Mountain Triplets I
  int minimumSum(vector<int>& nums) {
    const int n = nums.size();
    int ans = INT_MAX;
    vector<int> minPrefix(n);
    vector<int> minSuffix(n);

    partial_sum(nums.begin(), nums.end(), minPrefix.begin(),
                [](int x, int y) { return min(x, y); });
    partial_sum(nums.rbegin(), nums.rend(), minSuffix.begin(),
                [](int x, int y) { return min(x, y); });
    ranges::reverse(minSuffix);

    for (int i = 0; i < n; ++i)
      if (nums[i] > minPrefix[i] && nums[i] > minSuffix[i])
        ans = min(ans, nums[i] + minPrefix[i] + minSuffix[i]);

    return ans == INT_MAX ? -1 : ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  // Same as 2908. Minimum Sum of Mountain Triplets I
  public int minimumSum(int[] nums) {
    final int n = nums.length;
    int ans = Integer.MAX_VALUE;
    int[] minPrefix = new int[n];
    int[] minSuffix = new int[n];

    minPrefix[0] = nums[0];
    minSuffix[n - 1] = nums[n - 1];

    for (int i = 1; i < n; ++i)
      minPrefix[i] = Math.min(minPrefix[i - 1], nums[i]);

    for (int i = n - 2; i >= 0; --i)
      minSuffix[i] = Math.min(minSuffix[i + 1], nums[i]);

    for (int i = 0; i < n; ++i)
      if (nums[i] > minPrefix[i] && nums[i] > minSuffix[i])
        ans = Math.min(ans, nums[i] + minPrefix[i] + minSuffix[i]);

    return ans == Integer.MAX_VALUE ? -1 : ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  # Same as 2908. Minimum Sum of Mountain Triplets I
  def minimumSum(self, nums: list[int]) -> int:
    ans = math.inf
    minPrefix = list(itertools.accumulate(nums, min))
    minSuffix = list(itertools.accumulate(reversed(nums), min))[::-1]

    for i, num in enumerate(nums):
      if num > minPrefix[i] and num > minSuffix[i]:
        ans = min(ans, num + minPrefix[i] + minSuffix[i])

    return -1 if ans == math.inf else ans