algoadvance

Leetcode 2908. Minimum Sum of Mountain Triplets I

Problem Statement

You are given an integer array nums of length n. Your goal is to find three integers in nums that satisfy the following conditions:

  1. The integers are distinct.
  2. They form a mountain sequence such that a < b > c.
  3. Return the minimum sum of such mountain triplets. If there are no such triplets, return -1.

Example:

Input: nums = [2, 1, 3, 5, 4, 7]
Output: 10
Explanation: The mountain triplet [2, 5, 3] gives the sum as 10.

Clarifying Questions

  1. Q: Can the integers be non-consecutive in the array?
    • A: Yes, the integers do not need to be consecutive. They just need to satisfy the a < b > c condition.
  2. Q: Can the array contain duplicate values?
    • A: Yes, the array can contain duplicates, but the integers forming the triplet must be distinct.
  3. Q: Are there any constraints on the size of the input array?
    • A: Standard constraints apply, e.g., 1 <= nums.length <= 1000 and -10^4 <= nums[i] <= 10^4.

Strategy

To find the minimum sum of mountain triplets:

  1. Iterate through the array, considering each element as a potential peak b.
  2. For each possible peak b, find the largest possible a to the left of b and the largest possible c to the right of b.
  3. Track the minimum sum of any valid triplet found.

Steps:

  1. Initialization: Set initial minimum sum to a large value (e.g., Integer.MAX_VALUE).
  2. Iterate: Loop over the array considering each element as the peak of the mountain.
  3. Finding a (left of peak): Use a nested loop to find the largest element less than the peak before the index of the peak.
  4. Finding c (right of peak): Use a nested loop to find the largest element less than the peak after the index of the peak.
  5. Tracking Minimum: If both a and c are found, calculate the sum and update the minimum sum.

Code

public class Solution {
    public int minimumSumMountainTriplets(int[] nums) {
        int n = nums.length;
        int minSum = Integer.MAX_VALUE;
        boolean found = false;
        
        for (int j = 1; j < n - 1; j++) {
            int leftMax = Integer.MIN_VALUE;
            int rightMax = Integer.MIN_VALUE;

            // Look for the largest element to the left of nums[j]
            for (int i = 0; i < j; i++) {
                if (nums[i] < nums[j]) {
                    leftMax = Math.max(leftMax, nums[i]);
                }
            }

            // Look for the largest element to the right of nums[j]
            for (int k = j + 1; k < n; k++) {
                if (nums[k] < nums[j]) {
                    rightMax = Math.max(rightMax, nums[k]);
                }
            }

            if (leftMax != Integer.MIN_VALUE && rightMax != Integer.MIN_VALUE) {
                found = true;
                int currentSum = leftMax + nums[j] + rightMax;
                minSum = Math.min(minSum, currentSum);
            }
        }

        return found ? minSum : -1;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {2, 1, 3, 5, 4, 7};
        System.out.println(sol.minimumSumMountainTriplets(nums));  // Output: 10
    }
}

Time Complexity

Analysis:

Thus, the overall time complexity is O(n^2).

This solution is efficient given the constraints and ensures that all possible peaks are evaluated to find the minimum sum of mountain triplets.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI