2908. Minimum Sum of Mountain Triplets I

EasyArray
Leetcode Link

Problem Description

You are given an array of integers, where the array is indexed from 0 (0-indexed). The goal is to find a specific type of triplet within this array, referred to as a "mountain" triplet. A triplet (i, j, k) is defined as a mountain if it satisfies two conditions:

  • The indices are in increasing order: i < j < k.
  • The values at these indices increase and then decrease, forming a peak: nums[i] < nums[j] and nums[k] < nums[j].

Your task is to find such a mountain triplet whose sum of elements (nums[i] + nums[j] + nums[k]) is as small as possible and return this minimum sum. If no mountain triplet exists in the array, the function should return -1.

Intuition

The problem is to find three numbers that form a peak (or a mountain) with the smallest possible sum. We could try to look at every possible triplet in the array, but that would be slow as it would require checking n choose 3 triplets, where n is the size of the array.

To optimize the process, we can leverage the sequential nature of the triplets and use the concept of preprocessing. The main insight is that for a valid mountain triplet, the middle element must be greater than the elements to its left and right. So if we fix the middle element, we only need to find the smallest element to its left and the smallest to its right to minimize the sum.

The solution preprocesses the array to find the minimum value to the right of each element. It does so by traversing the array from right to left and keeps updating the minimum value seen so far. This information is stored in an array named right, where right[i] contains the minimum value in nums[i+1..n-1].

When we enumerate through each possible peak element nums[i], we keep track of the minimum value found to its left so far in a variable left. At the same time, we use a variable ans to maintain the current smallest sum found.

For each potential middle element nums[i], if it is greater than both the minimum to its left (left) and the minimum to its right (right[i+1]), it could be the peak of a minimum sum triplet. We update ans if the sum of these three elements is less than the current ans.

Finally, if ans is unchanged from inf, which is our initialization value representing infinity, it indicates that no mountain triplet was found, and we return -1. Otherwise, we return the value of ans.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Solution Approach

The solution makes intelligent use of a prefix and suffix strategy combined with a single pass through the array. The overall approach is to prepare in advance the information needed for a quick lookup and to use this information to find the minimum possible sum efficiently. Here's a breakdown of the implementation:

  1. First, we initialize an array right to keep track of the minimum values to the right of each index. This array is initially filled with inf (representing infinity), ensuring that if no smaller element exists to the right, the default large value prevents it from incorrectly contributing to a potential minimum triplet.

  2. We then fill the right array by iterating over nums backwards (from right to left). In each step, we assign to right[i] the minimum value between the current element nums[i] and the previously recorded minimum in right[i + 1]. This ensures that after this loop, for each index i, right[i] will contain the smallest element found in the subarray starting just after i until the end.

  3. We initialize two more variables before the main loop: left and ans. Both are set to inf. The left variable will hold the minimum value to the left of the current index as we scan the array. The ans variable will keep track of the minimum sum of any valid mountain triplet found so far.

  4. The main loop iterates over the elements of the nums array, attempting to find the smallest sum of a mountain triplet with the current element as the peak. For each element nums[i], we check two conditions to see if it can be the peak of a mountain triplet:

    • left < nums[i]: Is the current element greater than the smallest element found to its left?
    • right[i + 1] < nums[i]: Is the current element greater than the smallest element found to its right?

  5. If both conditions are satisfied, we then calculate the potential minimum sum of the mountain triplet, which is left + nums[i] + right[i + 1]. If this sum is less than what is stored in ans, we update ans with the new minimum sum.

  6. In the same iteration, we also update the left variable, setting it to be the minimum between its current value and the current element nums[i]. This ensures that left is always the smallest number to the left of the current element.

  7. After the loop completes, we check if ans has been updated from its initial value of inf. If ans is still inf, it means no valid mountain triplet was found, and we return -1. Otherwise, we return the value of ans, which is the minimum sum of a mountain triplet.

This solution cleverly avoids the need for a complex three-level nested loop, which would result in a less efficient algorithm with higher time complexity. Instead, it utilizes dynamic programming-like preprocessing and a single pass for a time-efficient linear scan of the array.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used in a depth first search?

Example Walkthrough

Let's illustrate the solution approach using a small example. Suppose we are given the following array of integers:

1nums = [2, 3, 1, 4, 3, 2]

  1. Initializing the right array: We first create an auxiliary array right with the same length as nums and initialize it with infinity values to avoid problems if no smaller right-hand side element is found. right = [inf, inf, inf, inf, inf, inf].

  2. Filling the right array: We fill right by iterating from right to left starting at index n - 2, where n is the length of nums. We have:

    15th step: right[4] = min(nums[4], right[5]) = min(3, inf) = 3
24th step: right[3] = min(nums[3], right[4]) = min(4, 3) = 3
33rd step: right[2] = min(nums[2], right[3]) = min(1, 3) = 1
42nd step: right[1] = min(nums[1], right[2]) = min(3, 1) = 1
51st step: right[0] = min(nums[0], right[1]) = min(2, 1) = 1

    Now, our right array looks like this: [1, 1, 1, 3, 3, inf].

  3. Iterating over nums: We declare left as infinity (inf) and ans also as infinity. These will track the minimum left element and the answer, respectively.

  4. Finding potential peaks: We iterate over the elements in the array:

    • For i = 0: left is inf, and the current element is 2, which is not greater than left or right[i + 1]. Thus, we skip this. We update left to 2.
    • For i = 1: left is 2, and the current element is 3, which is greater than left and right[i + 1]. The sum here would be 2 + 3 + 1 = 6. Since ans is inf, we update ans to 6. We update left to 2 (since min(2,3) = 2).
    • For i = 2: left remains 2, while right[i + 1] is 3. The current element is 1, so this cannot be a peak. We update left to 1.
    • For i = 3: left is 1, and the current element 4 is greater than both left and right[i + 1] which is 3. The sum is 1 + 4 + 3 = 8, but since ans is 6, we don't update ans. We update left to 1.
    • For i = 4 and i = 5: There are no elements to the right of i = 4 or i = 5 that are smaller than nums[i], so we do not find any valid mountain triplets.

  5. Checking and returning the answer: After this iteration, we find that ans holds the value 6, which is the minimum sum of a mountain triplet that we have found. This sum corresponds to the triplet (2, 3, 1) at indices (0, 1, 2).

Therefore, our function would return 6 as the smallest possible sum of a mountain triplet from the given nums array.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minimum_sum(self, nums: List[int]) -> int:
5        # Find the length of the nums list
6        num_elements = len(nums)
7      
8        # Initialize the 'right_min' list with infinities
9        # which will hold the minimum values from right
10        right_min = [float('inf')] * (num_elements + 1)
11      
12        # Populate the 'right_min' list with the minimum value
13        # from the current position to the end
14        for i in range(num_elements - 1, -1, -1):
15            right_min[i] = min(right_min[i + 1], nums[i])
16      
17        # Initialize 'result' (minimum sum) and 'left_min' with infinity
18        # 'left_min' will hold the minimum value from the start
19        # to the current position
20        result = left_min = float('inf')
21      
22        # Iterate through the numbers
23        for i, num in enumerate(nums):
24            # Check if both left and right numbers are less than the current number
25            # if yes, then calculate the result as current number plus left and right minimums
26            if left_min < num and right_min[i + 1] < num:
27                result = min(result, left_min + num + right_min[i + 1])
28          
29            # Update 'left_min' with the minimum value encountered so far
30            left_min = min(left_min, num)
31      
32        # If 'result' is still infinity, it means no valid sum was found
33        # return -1 in this case, otherwise return the computed result
34        return -1 if result == float('inf') else result
35
1class Solution {
2    public int minimumSum(int[] nums) {
3        int n = nums.length;
4        // Create an array to hold the minimum values from the right side.
5        int[] minRight = new int[n + 1];
6        final int INF = 1 << 30; // A representation of infinity (a very large number).
7        minRight[n] = INF; // Initialize the last element as infinity.
8      
9        // Populate the minRight array with the minimum values from the right side.
10        for (int i = n - 1; i >= 0; --i) {
11            minRight[i] = Math.min(minRight[i + 1], nums[i]);
12        }
13      
14        int answer = INF; // Initialize answer as infinity.
15        int minLeft = INF; // Variable to keep track of the minimum value from the left side.
16      
17        // Iterate through the array to find the minimum sum that follows the given constraint.
18        for (int i = 0; i < n; ++i) {
19            // Check if the current number is greater than both the minimum values on its left and right.
20            if (minLeft < nums[i] && minRight[i + 1] < nums[i]) {
21                // Update the answer with the sum of the smallest elements on both sides of nums[i].
22                answer = Math.min(answer, minLeft + nums[i] + minRight[i + 1]);
23            }
24            // Update the minimum value from the left side.
25            minLeft = Math.min(minLeft, nums[i]);
26        }
27      
28        // If the answer remains infinity, it means there were no valid sums found, so return -1.
29        return answer == INF ? -1 : answer;
30    }
31}
32
1class Solution {
2public:
3    int minimumSum(vector<int>& nums) {
4        // Get the size of the vector
5        int size = nums.size();
6
7        // Define an infinite value for comparison purposes
8        const int INF = 1 << 30;
9
10        // Create a vector to store the minimum from the right of each position, initialize with INF at the end
11        vector<int> minRight(size + 1, INF);
12
13        // Populate minRight with the minimum value from the right side in reverse order
14        for (int i = size - 1; i >= 0; --i) {
15            minRight[i] = min(minRight[i + 1], nums[i]);
16        }
17
18        // Initialize variables to store the minimum sum and the minimum on the left
19        int minimumSum = INF;
20        int minLeft = INF;
21
22        // Iterate through numbers, updating minLeft and checking for a potential minimum sum
23        for (int i = 0; i < size; ++i) {
24            // If the current element is greater than the minimum on the left and right,
25            // attempt to update the minimum sum
26            if (minLeft < nums[i] && minRight[i + 1] < nums[i]) {
27                minimumSum = min(minimumSum, minLeft + nums[i] + minRight[i + 1]);
28            }
29            // Update the minimum on the left with the current element
30            minLeft = min(minLeft, nums[i]);
31        }
32
33        // If minimumSum remains INF, no valid sum is found; thus, return -1
34        // Otherwise, return the calculated minimum sum
35        return minimumSum == INF ? -1 : minimumSum;
36    }
37};
38
1function minimumSum(nums: number[]): number {
2    // Calculate the length of nums array
3    const length = nums.length;
4    // Create an array 'rightMin' to store minimum values to the right of each element
5    const rightMin: number[] = Array(length + 1).fill(Infinity);
6
7    // Populate 'rightMin' with the minimum values observed from the end of the array
8    for (let i = length - 1; i >= 0; i--) {
9        rightMin[i] = Math.min(rightMin[i + 1], nums[i]);
10    }
11
12    // Initialize 'minimumSum' as Infinity to track the minimum sum of non-adjacent array elements
13    let minimumSum: number = Infinity;
14    // Initialize 'leftMin' as Infinity to track the minimum value to the left of current index
15    let leftMin: number = Infinity;
16
17    // Iterate over the 'nums' array to find the minimum sum of non-adjacent array elements
18    for (let i = 0; i < length; i++) {
19        // Check current element with minimum elements from both sides (excluding adjacent elements)
20        if (leftMin < nums[i] && rightMin[i + 1] < nums[i]) {
21            // Update 'minimumSum' if the current triplet sum is smaller than the previously found
22            minimumSum = Math.min(minimumSum, leftMin + nums[i] + rightMin[i + 1]);
23        }
24        // Update 'leftMin' with the minimum value found so far from the left
25        leftMin = Math.min(leftMin, nums[i]);
26    }
27
28    // If 'minimumSum' is still Infinity, it means no triplet was found, return -1
29    // Otherwise, return the minimum sum calculated
30    return minimumSum === Infinity ? -1 : minimumSum;
31}
32
Not Sure What to Study? Take the 2-min Quiz：

Which of these properties could exist for a graph but not a tree?

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n).

  1. The first for loop iterates from n-1 to 0, which results in n iterations.
  2. The second for loop iterates from 0 to n-1, which is also n iterations.

Each of these loops runs in linear time relative to the number of elements n in the list nums. There are no nested loops, and each operation inside the loops runs in constant time O(1). Hence, adding the time cost gives us a time complexity that is still linear: O(n) + O(n) = O(2n) which simplifies to O(n).

Space Complexity

The space complexity of the given code is O(n).

The code uses an additional list right of size n+1 elements to keep track of the minimum elements to the right. Aside from the right list and trivial variables (ans, left, i, and x), no additional space that scales with input size n is used. Therefore, the space complexity is determined by the right list, giving O(n + 1); this simplifies to O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫