2873. Maximum Value of an Ordered Triplet I
Problem Description
You are provided with an array of integers, nums
, which has a 0-based index. The goal is to find the maximum value of a triplet (i, j, k)
in this array, following the condition that i
, j
, and k
are distinct indices, with i
being less than j
, and j
being less than k
. In other words, you need to find the maximum value obtained from the formula (nums[i] - nums[j]) * nums[k]
across all possible combinations of triplets.
In a case where the values for all possible triplets are negative, the result should be 0
.
The problem asks for the efficient computation of this value without having to compare every possible triplet directly, which would be inefficient for large arrays.
Intuition
To avoid an exhaustive search which is highly inefficient, we observe that we can solve the problem by keeping track of two pieces of information as we iterate through the array from left to right.
-
mx
: This is the maximum value found innums
up to the current point in our traversal. We can think of it as the 'best' first elementnums[i]
seen so far for any triplet. -
mx_diff
: This represents the maximum value ofmx - nums[j]
, which is the first part of our target equation(nums[i] - nums[j])
. It essentially stores the best-case scenario for the difference between the first and second elements of our triplet encountered so far.
As we traverse the array, at each step, we attempt to update mx_diff
with the largest possible value by considering the current mx
and the current number num
as if it were nums[j]
. We also update mx
if the current number is larger than the current mx
. After updating mx
and mx_diff
, we then calculate the potential best-case scenario for the triplet value with the current number as nums[k]
, and update the answer if it's greater than the current answer.
The intuition behind this approach is that we are dynamically keeping track of the best possible scenario for the first two numbers of the triplet as we progress. When we reach any nums[k]
, we have already computed the best possible nums[i]
and nums[j]
that could precede it, thus allowing us to directly calculate the best possible value for (nums[i] - nums[j]) * nums[k]
with the elements we've passed by so far.
Solution Approach
The solution implements a single pass approach, traversing the list once, which keeps it very efficient in terms of both time and space complexity. The algorithm does not use any extra data structures, as it simply maintains two variables mx
and mx_diff
to track the maximum value found so far and the maximum difference encountered so far, respectively.
The approach makes use of the following steps:
-
Initialize
ans
,mx
, andmx_diff
as zero.ans
will hold the answer to be returned,mx
is used to keep track of the maximum value innums
as we iterate, andmx_diff
keeps track of the maximum value ofmx - nums[j]
found so far. -
Loop through each element
num
innums
. For eachnum
:- Update the
ans
if the currentmx_diff * num
is greater thanans
. This step checks if the current number asnums[k]
combined with the bestmx_diff
so far makes for a higher product than we've seen. - Update
mx
ifnum
is greater thanmx
. This step simply keepsmx
as the maximum value seen up to the current element in the array, representing the best choice fornums[i]
up to this point. - Update
mx_diff
ifmx - num
is greater thanmx_diff
. By doing this, you are ensuring thatmx_diff
holds the largest possible difference between the bestnums[i]
and anynums[j]
seen so far.
- Update the
During each iteration, the algorithm dynamically updates the potential first two elements of the triplet, which allows it to calculate the potential best-case scenario for the triplet value in constant time.
By maintaining the maximum found value and the maximum difference during the iteration, the algorithm eliminates the need to check every possible combination of i
, j
, and k
, which is the key to its efficiency.
Here is the pseudocode that captures the essence of the implementation:
def maximumTripletValue(nums):
ans = mx = mx_diff = 0
for num in nums:
ans = max(ans, mx_diff * num)
mx = max(mx, num)
mx_diff = max(mx_diff, mx - num)
return ans
This algorithm runs in O(n)
time, where n
is the length of the input array, making it extremely efficient for large datasets.
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 consider a small example array nums
to illustrate the solution approach.
Example nums
array: [3, 1, 6, 4]
We have to find the maximum value of the expression (nums[i] - nums[j]) * nums[k]
with the constraints i < j < k
.
We initialize ans
, mx
, and mx_diff
to 0
.
-
We start with the first element
3
:mx
is updated to3
because it's the only element we've seen.mx_diff
remains0
because we don't have aj
yet.ans
remains0
for the same reason.
After the first iteration:
ans = 0
,mx = 3
,mx_diff = 0
. -
Moving to the second element
1
:- We consider the element
1
as potentialnums[j]
. The differencemx - num
is3 - 1 = 2
. mx_diff
is updated to2
because2
is greater than the currentmx_diff
which is0
.ans
is still0
as we have not yet encountered a validk
.
After the second iteration:
ans = 0
,mx = 3
,mx_diff = 2
. - We consider the element
-
Next, we process the third element
6
:- This element is considered as potential
nums[k]
. We computemx_diff * num
which is2 * 6 = 12
. ans
is updated to12
because12
is greater than the currentans
which is0
.- Now we update
mx
to6
because6
is greater than the currentmx
which is3
. mx_diff
does not change becausemx - num
is-3
which is not greater than2
.
After the third iteration:
ans = 12
,mx = 6
,mx_diff = 2
. - This element is considered as potential
-
Finally, we look at the fourth element
4
:- We calculate
mx_diff * num
which is2 * 4 = 8
. However,ans
remains12
because8
is not greater than12
. mx
does not change because4
is not greater than6
.mx_diff
is updated, asmx - num
is6 - 4 = 2
, but sincemx_diff
is already2
, it remains the same.
After the fourth and final iteration:
ans = 12
,mx = 6
,mx_diff = 2
. - We calculate
At the end of the iterations, the maximum value found for the expression (nums[i] - nums[j]) * nums[k]
is 12
, which is the final answer. The triplet that gives us this value is (3, 1, 6)
where i = 0
, j = 1
, and k = 2
. Therefore, the function maximumTripletValue
with the array [3, 1, 6, 4]
as input will return 12
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def maximumTripletValue(self, nums: List[int]) -> int:
5 # Initialize variables:
6 # max_product - to keep track of the maximum product of max_difference and the current number,
7 # max_number - to store the maximum value encountered so far,
8 # max_difference - to store the maximum difference between max_number and any other number.
9 max_product = 0
10 max_number = 0
11 max_difference = 0
12
13 # Iterate through all numbers in the list.
14 for num in nums:
15 # Update max_product with the maximum product obtained
16 # by multiplying max_difference with the current num.
17 max_product = max(max_product, max_difference * num)
18
19 # Update max_number if the current num is greater than the previously stored max_number.
20 max_number = max(max_number, num)
21
22 # Update max_difference if the difference between the current max_number and num
23 # is greater than the previously stored max_difference.
24 # This difference represents a potential first and second element of a triplet,
25 # with num potentially being the third element.
26 max_difference = max(max_difference, max_number - num)
27
28 # After iterating through all numbers, max_product will hold
29 # the maximum product of a triplet's first and third elements.
30 return max_product
31
1class Solution {
2 public long maximumTripletProduct(int[] nums) {
3 long maxVal = 0; // Initialize maximum value found in the array to 0
4 long maxDiff = 0; // Initialize maximum difference between maxVal and any other value to 0
5 long answer = 0; // Initialize the result for the maximum product of the triplet
6
7 // Iterate through all elements in the nums array
8 for (int num : nums) {
9 // Update the answer with the maximum between the current max product
10 // or the product of the current number and maxDiff
11 answer = Math.max(answer, num * maxDiff);
12
13 // Update maxVal with the maximum between the current maxVal or the current number
14 maxVal = Math.max(maxVal, num);
15
16 // Update maxDiff with the maximum difference found so far
17 maxDiff = Math.max(maxDiff, maxVal - num);
18 }
19
20 // Return the maximum product of a triplet found in the array
21 return answer;
22 }
23}
24
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Solution {
6public:
7 // Function to calculate the maximum product of a triplet in the array such that
8 // the indices of the triplet (i, j, k) satisfy i < j < k and nums[i] < nums[j] < nums[k].
9 long long maximumTripletValue(vector<int>& nums) {
10 long long maxProduct = 0; // To store the maximum product of a triplet
11 int maxElement = 0; // To store the maximum element seen so far
12 int maxDifference = 0; // To store the maximum difference seen so far
13
14 // Loop through each number in the array 'nums'
15 for (int num : nums) {
16 // Update maxProduct with the maximum between current maxProduct and the product
17 // of maxDifference and the current number 'num'. This accounts for the third element of the triplet.
18 maxProduct = max(maxProduct, static_cast<long long>(maxDifference) * num);
19
20 // Update maxElement with the maximum between current maxElement and the current number 'num'
21 maxElement = max(maxElement, num);
22
23 // Update maxDifference with the maximum difference between maxElement and the current number 'num'
24 maxDifference = max(maxDifference, maxElement - num);
25 }
26
27 // Return the maximum product of a triplet found in the array
28 return maxProduct;
29 }
30};
31
1// Calculates the maximum product of any triplet in the given array
2// that can be formed by multiplying any three numbers which indices
3// are strictly in increasing order.
4function maximumTripletValue(nums: number[]): number {
5 let maxProduct = 0; // Variable to store the maximum product found
6 let maxNum = 0; // Variable to store the maximum number found so far
7 let maxDifference = 0; // Variable to store the maximum difference found so far
8
9 // Iterate through the array of numbers
10 for (const num of nums) {
11 // Update the maxProduct with the maximum between the current maxProduct and
12 // the product of num and maxDifference which represents a potential triplet product
13 maxProduct = Math.max(maxProduct, maxDifference * num);
14 // Update the maxNum with the greatest number encountered so far
15 maxNum = Math.max(maxNum, num);
16 // Update the maxDifference with the greatest difference between maxNum and the current num
17 maxDifference = Math.max(maxDifference, maxNum - num);
18 }
19
20 // Return the maximum product found for the triplet
21 return maxProduct;
22}
23
Time and Space Complexity
The time complexity of the given code segment is O(n)
, where n
is the length of the array nums
. This is because there is a single for-loop that iterates over all the elements in the array once.
The space complexity is O(1)
since the extra space used does not grow with the input size; only a fixed number of variables ans
, mx
, and mx_diff
are used regardless of the size of the input array.
Learn more about how to find time and space complexity quickly using problem constraints.
In a binary min heap, the minimum element can be found in:
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
Want a Structured Path to Master System Design Too? Donāt Miss This!