2874. Maximum Value of an Ordered Triplet II
Problem Description
In this problem, we are given an array of integers, nums
, indexed starting from 0. The task is to find the maximum value that can be obtained from choosing any three different indices (i, j, k)
in the array such that i < j < k
. The value of a triplet (i, j, k)
is calculated using the formula (nums[i] - nums[j]) * nums[k]
.
If we consider different combinations of three elements from the array, some might yield negative values, while others might yield positive values or zero. We want to find the maximum positive value, or if all the possible triplets result in a negative value, we return 0
.
To understand the value of a triplet, let's consider that nums[i]
is greater than nums[j]
, then (nums[i] - nums[j])
will be positive. In this case, to maximize the value of the triplet, you would want nums[k]
to be as large as possible because you are multiplying by nums[k]
. If nums[i]
is less than nums[j]
, the difference becomes negative, and a large nums[k]
will only lead to a more negative value. In that case, we are not interested in those combinations as our goal is to find the maximum positive value.
Intuition
The intuition behind the solution is to traverse the array while keeping track of two key values: the maximum value found so far (mx
), and the maximum difference between mx
and the current value (mx_diff
). These two variables help in efficiently computing the maximum value of the triplet without having to explicitly check all possible triplet combinations.
The maximum prefix value mx
represents the largest number we have seen so far as we iterate through the array. This value could potentially be nums[i]
of our triplet. As we are looking for i < j < k
, any number we see can be a candidate for nums[k]
.
The maximum difference mx_diff
represents the highest value obtained from subtracting any previously encountered number from mx
. It effectively keeps track of the maximum (nums[i] - nums[j])
that we have seen so far.
While we iterate through the array, for any current number num
, we calculate and update ans
with max(ans, mx_diff * num)
. This step calculates the maximum triplet value for the current number as nums[k]
(since num
is always the right-most element in the potential triplet). We ensure to first update ans
before updating mx_diff
because mx_diff
needs to be the result of the prefix, not including the current number.
By following this approach, we avoid having to compare each possible triplet explicitly, which would result in a higher computational complexity. Instead, we make use of the information that is gathered while traversing through the array to keep updating our potential maximum triplet value, all in linear time which is efficient.
Solution Approach
The approach is to cleverly keep track of the necessary values as we iterate through the array, enabling us to calculate the maximum triplet value on the fly without the need to consider each triplet individually.
When we start iterating through the array nums
, we initialize two variables mx
and mx_diff
with zero. mx
will keep track of the maximum value we have encountered so far (i.e., the maximum value for nums[i]
), and mx_diff
will store the maximum difference computed as (nums[i] - nums[j])
during the iteration.
Below are the steps that we perform as we traverse the array nums
from left to right:
-
Update the Answer: For the current value
num
innums
, we attempt to update the answer,ans
, with the maximum of eitherans
itself or the product ofmx_diff
andnum
. The reason behind this calculation is thatnum
will serve asnums[k]
(the potential third element in our triplet), andmx_diff
represents the maximum difference from previous elementsnums[i]
andnums[j]
. This step ensures that we always have the maximum possible product for the current state of the array.ans = max(ans, mx_diff * num)
-
Update Maximum Value: Next, we update
mx
to be the maximum of itself or the current valuenum
, because as we move through the array, we need to keep track of the largest value seen so far that could becomenums[i]
for future triplets.mx = max(mx, num)
-
Update Maximum Difference: Finally, we update
mx_diff
. To maintain the invariant thatmx_diff
is the maximum difference for a valid triplet, we must ensure that it is always calculated uptil the elements beforenum
(asnum
is a candidate fornums[k]
). Hence, it is updated as the maximum of itself ormx - num
.mx_diff = max(mx_diff, mx - num)
Since we always update ans
before mx_diff
, we can guarantee that the difference applied to the calculation of ans
doesn't include the current num
as mx_diff
gets updated only after ans
.
This way, as we move forward through the array, we dynamically update and maintain the necessary values to find the maximum triplet product based on the constraints given in the problem. The final answer is stored in ans
, which by the end of the iteration of the array contains the maximum value for all the valid triplets (i, j, k)
that we were tasked with finding.
The algorithm leverages two fundamental ideas:
- Dynamic Updates: Instead of considering every triplet separately, it keeps track of the potential maximums dynamically.
- Greedy Choice Property: By choosing the best options at each step (maximum value and maximum difference), we ensure the end result is optimal.
This concise yet effective approach and the minimal use of extra space (just two variables) contributes to an efficient solution with linear time complexity O(n)
and constant space complexity O(1)
.
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 walk through a small example to illustrate the solution approach. Consider the array nums = [1, 5, 6, 3, 7]
. We need to find the maximum value of (nums[i] - nums[j]) * nums[k]
where i < j < k
.
We start by initializing mx
and mx_diff
as 0
. The variable ans
will be used to keep track of the maximum value we find.
- We begin with the first element
1
.mx
is updated to1
(it's the first element). There are no previous elements to consider, so we move to the next element. - At element
5
, we updatemx
to5
(since5
is greater thanmx
which was1
). We cannot updatemx_diff
yet since we do not have aj
index. - Moving to element
6
,mx
remains at5
.mx_diff
is updated to0
(which was5 - 5
, the only pair we've considered). We can now consider the difference between the currentmx
andnums[j]
which is from previous elements. However, we do not updateans
since we still need ak
index. - At element
3
,mx
is not updated since3
is not greater than5
.mx_diff
can be updated to2
(mx
which is5
minus current element3
). The answerans
is now the maximum of0
andmx_diff * num
, which is2 * 3 = 6
. - Finally, we arrive at element
7
.mx
is not updated since7
is not greater than currentmx
which is5
. We then calculateans
as the maximum of6
andmx_diff * num
, which is2 * 7 = 14
. Thus,ans
is updated to14
.mx_diff
is updated to4
(since5
-3
was less than5
-1
which is4
).
After the iteration, ans
holds the value 14
, which is the maximum value for the expression (nums[i] - nums[j]) * nums[k]
.
To summarize, the steps were as follows:
nums[0] = 1
: Initializemx = 1
,mx_diff = 0
,ans = 0
.nums[1] = 5
: Updatemx = 5
.ans
andmx_diff
cannot be updated as we need ak
.nums[2] = 6
:mx_diff
can now be calculated, but remains0
,mx
remains5
.nums[3] = 3
: Updatemx_diff = 2
. Updateans = max(0, 2 * 3) = 6
.nums[4] = 7
: Do not updatemx
but updateans = max(6, 2 * 7) = 14
. Updatemx_diff = max(2, 5 - 3) = 4
.
The procedure efficiently finds the maximum value by dynamically updating the mx
, mx_diff
, and ans
variables while traversing the array a single time. The solution did not require examining all possible triplets, thus maintaining a linear time complexity.
Solution Implementation
1# Import typing List to specify the type of the input nums.
2from typing import List
3
4class Solution:
5 def maximumTripletValue(self, nums: List[int]) -> int:
6 # Initialize variables to store the maximum triplet value, the maximum number encountered so far,
7 # and the maximum difference between the maximum number and the current number.
8 max_triplet_value = 0
9 max_number = 0
10 max_difference = 0
11
12 # Iterate through each number in the input list.
13 for number in nums:
14 # Calculate the maximum triplet value by taking the maximum between the current max_triplet_value
15 # and the product of max_difference and the current number.
16 max_triplet_value = max(max_triplet_value, max_difference * number)
17
18 # Update max_number if the current number is greater than the max_number seen so far.
19 max_number = max(max_number, number)
20
21 # Update max_difference which is the maximum difference found between max_number and any number.
22 max_difference = max(max_difference, max_number - number)
23
24 # Return the maximum possible triplet value found.
25 return max_triplet_value
26
1class Solution {
2
3 // Method to calculate the maximum triplet value.
4 public long maximumTripletValue(int[] nums) {
5 // Initialize three variables to store the current maximum value,
6 // the maximum difference found so far, and the answer we will return.
7 long currentMax = 0;
8 long maximumDiff = 0;
9 long answer = 0;
10
11 // Iterate through each number in the array.
12 for (int num : nums) {
13 // Calculate the tentative answer as the current number times the maximum difference,
14 // update the answer if the result is greater than the current answer.
15 answer = Math.max(answer, num * maximumDiff);
16
17 // Update currentMax if the current number is greater than currentMax.
18 currentMax = Math.max(currentMax, num);
19
20 // Update maximumDiff if the difference between currentMax and current number
21 // is greater than maximumDiff.
22 maximumDiff = Math.max(maximumDiff, currentMax - num);
23 }
24
25 // Return the final answer.
26 return answer;
27 }
28}
29
1#include <vector>
2#include <algorithm> // Include necessary headers for vector and max function
3
4class Solution {
5public:
6 long long maximumTripletValue(std::vector<int>& nums) {
7 long long maxTripletValue = 0; // This will hold the maximum value of the triplet found so far
8 int maxNum = 0; // This will keep track of the maximum number encountered in the array
9 int maxDifference = 0; // This will keep the maximum difference we've found between maxNum and a smaller number
10
11 // Iterate over the elements of nums
12 for (int num : nums) {
13 // Update the maximum value of any triplet found so far.
14 // The maximum triplet value is defined by maxDifference multiplied by the current number.
15 maxTripletValue = std::max(maxTripletValue, 1LL * maxDifference * num);
16
17 // Update maxNum if the current number is greater than the previous maxNum.
18 maxNum = std::max(maxNum, num);
19
20 // Update maxDifference if the difference between the current maxNum and num is greater
21 // than the previous maxDifference.
22 maxDifference = std::max(maxDifference, maxNum - num);
23 }
24
25 return maxTripletValue; // Return the maximum triplet value found.
26 }
27};
28
1function maximumTripletValue(nums: number[]): number {
2 // Initialize variables:
3 // ans - to store the maximum product of the triplet.
4 // maxNum - to store the maximum number encountered so far.
5 // maxDifference - to store the maximum difference encountered so far.
6 let [maxProduct, maxNum, maxDifference] = [0, 0, 0];
7
8 // Loop through each number in the array to calculate the maximum triplet value.
9 for (const num of nums) {
10 // Update the maxProduct with the maximum of current maxProduct and
11 // the product of maxDifference and the current num.
12 maxProduct = Math.max(maxProduct, maxDifference * num);
13
14 // Update maxNum with the maximum of current maxNum and the current num.
15 maxNum = Math.max(maxNum, num);
16
17 // Update maxDifference with the maximum of current maxDifference and
18 // the difference between current maxNum and the current num.
19 maxDifference = Math.max(maxDifference, maxNum - num);
20 }
21
22 // Return the calculated maximum product of a triplet.
23 return maxProduct;
24}
25
Time and Space Complexity
The time complexity of the provided code is O(n)
because there is a single for loop that iterates through the array nums
once. Each operation inside the loop, such as updating ans
, mx
, and mx_diff
, is done in constant time, independent of the size of the input array. As the loop runs n
times, where n
is the length of the array, the overall time complexity is linear.
The space complexity of the code is O(1)
. The reason for this constant space complexity is that only a fixed number of variables (ans
, mx
, and mx_diff
) are used. These variables do not depend on the size of the input, hence, the amount of allocated memory stays constant regardless of the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
What data structure does Breadth-first search typically uses to store intermediate states?
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
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.