2874. Maximum Value of an Ordered Triplet II

MediumArray
Leetcode Link

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.

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

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

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:

  1. Update the Answer: For the current value num in nums, we attempt to update the answer, ans, with the maximum of either ans itself or the product of mx_diff and num. The reason behind this calculation is that num will serve as nums[k] (the potential third element in our triplet), and mx_diff represents the maximum difference from previous elements nums[i] and nums[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)

  2. Update Maximum Value: Next, we update mx to be the maximum of itself or the current value num, because as we move through the array, we need to keep track of the largest value seen so far that could become nums[i] for future triplets.

    mx = max(mx, num)

  3. Update Maximum Difference: Finally, we update mx_diff. To maintain the invariant that mx_diff is the maximum difference for a valid triplet, we must ensure that it is always calculated uptil the elements before num (as num is a candidate for nums[k]). Hence, it is updated as the maximum of itself or mx - 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).

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

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

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

  1. We begin with the first element 1. mx is updated to 1 (it's the first element). There are no previous elements to consider, so we move to the next element.
  2. At element 5, we update mx to 5 (since 5 is greater than mx which was 1). We cannot update mx_diff yet since we do not have a j index.
  3. Moving to element 6, mx remains at 5. mx_diff is updated to 0 (which was 5 - 5, the only pair we've considered). We can now consider the difference between the current mx and nums[j] which is from previous elements. However, we do not update ans since we still need a k index.
  4. At element 3, mx is not updated since 3 is not greater than 5. mx_diff can be updated to 2 (mx which is 5 minus current element 3). The answer ans is now the maximum of 0 and mx_diff * num, which is 2 * 3 = 6.
  5. Finally, we arrive at element 7. mx is not updated since 7 is not greater than current mx which is 5. We then calculate ans as the maximum of 6 and mx_diff * num, which is 2 * 7 = 14. Thus, ans is updated to 14. mx_diff is updated to 4 (since 5 - 3 was less than 5 - 1 which is 4).

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: Initialize mx = 1, mx_diff = 0, ans = 0.
  • nums[1] = 5: Update mx = 5. ans and mx_diff cannot be updated as we need a k.
  • nums[2] = 6: mx_diff can now be calculated, but remains 0, mx remains 5.
  • nums[3] = 3: Update mx_diff = 2. Update ans = max(0, 2 * 3) = 6.
  • nums[4] = 7: Do not update mx but update ans = max(6, 2 * 7) = 14. Update mx_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
Not Sure What to Study? Take the 2-min Quiz：

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following shows the order of node visit in a Breadth-first Search?

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 👨‍🏫