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 in nums up to the current point in our traversal. We can think of it as the 'best' first element nums[i] seen so far for any triplet.

  • mx_diff: This represents the maximum value of mx - 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, and mx_diff as zero. ans will hold the answer to be returned, mx is used to keep track of the maximum value in nums as we iterate, and mx_diff keeps track of the maximum value of mx - nums[j] found so far.

  • Loop through each element num in nums. For each num:

    • Update the ans if the current mx_diff * num is greater than ans. This step checks if the current number as nums[k] combined with the best mx_diff so far makes for a higher product than we've seen.
    • Update mx if num is greater than mx. This step simply keeps mx as the maximum value seen up to the current element in the array, representing the best choice for nums[i] up to this point.
    • Update mx_diff if mx - num is greater than mx_diff. By doing this, you are ensuring that mx_diff holds the largest possible difference between the best nums[i] and any nums[j] seen so far.

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:

1def maximumTripletValue(nums):
2    ans = mx = mx_diff = 0
3    for num in nums:
4        ans = max(ans, mx_diff * num)
5        mx = max(mx, num)
6        mx_diff = max(mx_diff, mx - num)
7    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.

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

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Example 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.

  1. We start with the first element 3:

    • mx is updated to 3 because it's the only element we've seen.
    • mx_diff remains 0 because we don't have a j yet.
    • ans remains 0 for the same reason.

    After the first iteration: ans = 0, mx = 3, mx_diff = 0.

  2. Moving to the second element 1:

    • We consider the element 1 as potential nums[j]. The difference mx - num is 3 - 1 = 2.
    • mx_diff is updated to 2 because 2 is greater than the current mx_diff which is 0.
    • ans is still 0 as we have not yet encountered a valid k.

    After the second iteration: ans = 0, mx = 3, mx_diff = 2.

  3. Next, we process the third element 6:

    • This element is considered as potential nums[k]. We compute mx_diff * num which is 2 * 6 = 12.
    • ans is updated to 12 because 12 is greater than the current ans which is 0.
    • Now we update mx to 6 because 6 is greater than the current mx which is 3.
    • mx_diff does not change because mx - num is -3 which is not greater than 2.

    After the third iteration: ans = 12, mx = 6, mx_diff = 2.

  4. Finally, we look at the fourth element 4:

    • We calculate mx_diff * num which is 2 * 4 = 8. However, ans remains 12 because 8 is not greater than 12.
    • mx does not change because 4 is not greater than 6.
    • mx_diff is updated, as mx - num is 6 - 4 = 2, but since mx_diff is already 2, it remains the same.

    After the fourth and final iteration: ans = 12, mx = 6, mx_diff = 2.

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.


Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?


Recommended Readings


Got a question? Ask the Monster 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.


🪄