2909. Minimum Sum of Mountain Triplets II

Time: O(n)

Space: O(n)

Approach

Precompute prefix min left and suffix min right; scan middle finding valid mountain triplets.

Key Techniques

Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.

Sorting

Sorting is often a preprocessing step that enables binary search, two-pointer sweeps, or greedy algorithms. C#'s Array.Sort() uses an introspective sort (O(n log n)). Custom comparisons use the Comparison<T> delegate or IComparer<T>. Consider counting sort or bucket sort for bounded integer inputs.

2909.cs

// Approach: Precompute prefix min left and suffix min right; scan middle finding valid mountain triplets.
// Time: O(n) Space: O(n)

public class Solution
{
    public int MinimumSum(int[] nums)
    {
        int n = nums.Length;
        int ans = int.MaxValue;
        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 == int.MaxValue ? -1 : ans;
    }
}

Was this solution helpful?