Leetcode 2909 - Minimum Sum of Mountain Triplets II

Link to problem
Also check here

Description

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. If no such triplet exists, return -1.

Solution

Saw this problem on Leetcode’s Weekly Contest 368. The contest also includes Leetcode 2908, which is basically the same problem but with smaller test data that we could brute force it.

Back to solving the problem.

We are finding the minimum triplets, of index (i, j, k) where i < j < k. nums[i] and nums[k] will apparently be the smallest number before / after index j. However, we want to avoid searching the smallest numbers before j and smallest numbers after j by iterating every index j.

To solve this, we could build two arrays to store the minimum number up to this point, one iterates forward and another backwards.

Then we iterate through the array nums once more to get the minimum sum. The time complexity for this algorithm will be $O(n)$.

Implementation

class Solution {
public:
    int minimumSum(vector<int>& nums) {
        size_t n = nums.size();
        int output = numeric_limits<int>::max();
        vector<int> leftMin(n, numeric_limits<int>::max());
        vector<int> rightMin(n, numeric_limits<int>::max());
        leftMin[0] = nums[0];
        rightMin[n-1] = nums[n-1];

        for (size_t i = 1; i < n; i++) {
            leftMin[i] = min(leftMin[i-1], nums[i]);
            rightMin[n-i-1] = min(rightMin[n-i], nums[n-i-1]);
        }

        for (size_t i = 1; i < n-1; i++) {
            if (leftMin[i-1] < nums[i] && rightMin[i+1] < nums[i])
                output = min(output, leftMin[i-1] + rightMin[i+1] + nums[i]);
        }

        return (output == numeric_limits<int>::max()? -1: output);
    }
};

Things didn’t go well…

For some reason, I did not solve this problem during contest but managed to do it in 5 minutes the day after. And out of pride or something about holding a masters degree in computer science, I refused to solve it by brute force to at least get the points from the first problem(the same question with smaller size test data). feels_bad_man.png