2908. Minimum Sum of Mountain Triplets I
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]
andnums[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
.
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:
-
First, we initialize an array
right
to keep track of the minimum values to the right of each index. This array is initially filled withinf
(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. -
We then fill the
right
array by iterating overnums
backwards (from right to left). In each step, we assign toright[i]
the minimum value between the current elementnums[i]
and the previously recorded minimum inright[i + 1]
. This ensures that after this loop, for each indexi
,right[i]
will contain the smallest element found in the subarray starting just afteri
until the end. -
We initialize two more variables before the main loop:
left
andans
. Both are set toinf
. Theleft
variable will hold the minimum value to the left of the current index as we scan the array. Theans
variable will keep track of the minimum sum of any valid mountain triplet found so far. -
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 elementnums[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?
-
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 inans
, we updateans
with the new minimum sum. -
In the same iteration, we also update the
left
variable, setting it to be the minimum between its current value and the current elementnums[i]
. This ensures thatleft
is always the smallest number to the left of the current element. -
After the loop completes, we check if
ans
has been updated from its initial value ofinf
. Ifans
is stillinf
, it means no valid mountain triplet was found, and we return-1
. Otherwise, we return the value ofans
, 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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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]
-
Initializing the
right
array: We first create an auxiliary arrayright
with the same length asnums
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]
. -
Filling the
right
array: We fillright
by iterating from right to left starting at indexn - 2
, wheren
is the length ofnums
. 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]
. -
Iterating over
nums
: We declareleft
as infinity (inf
) andans
also as infinity. These will track the minimum left element and the answer, respectively. -
Finding potential peaks: We iterate over the elements in the array:
- For
i = 0
:left
isinf
, and the current element is2
, which is not greater thanleft
orright[i + 1]
. Thus, we skip this. We updateleft
to2
. - For
i = 1
:left
is2
, and the current element is3
, which is greater thanleft
andright[i + 1]
. The sum here would be2 + 3 + 1 = 6
. Sinceans
isinf
, we updateans
to6
. We updateleft
to2
(sincemin(2,3) = 2
). - For
i = 2
:left
remains2
, whileright[i + 1]
is3
. The current element is1
, so this cannot be a peak. We updateleft
to1
. - For
i = 3
:left
is1
, and the current element4
is greater than bothleft
andright[i + 1]
which is3
. The sum is1 + 4 + 3 = 8
, but sinceans
is6
, we don't updateans
. We updateleft
to1
. - For
i = 4
andi = 5
: There are no elements to the right ofi = 4
ori = 5
that are smaller thannums[i]
, so we do not find any valid mountain triplets.
- For
-
Checking and returning the answer: After this iteration, we find that
ans
holds the value6
, 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
Time and Space Complexity
Time Complexity
The time complexity of the given code is O(n)
.
- The first
for
loop iterates fromn-1
to0
, which results inn
iterations. - The second
for
loop iterates from0
ton-1
, which is alson
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.
Which two pointer techniques do you use to check if a string is a palindrome?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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 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