#2874

Medium

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Maximum Value of an Ordered Triplet II

Solve Maximum Value of an Ordered Triplet II in linear time by tracking the best left difference and right multiplier.

Problem Statement

You need the largest value of (nums[i] - nums[j]) * nums[k] where the indices stay in order, so i comes before j and j comes before k. Because the array is 0-indexed and can be large, the core challenge is not the formula itself but preserving the ordering while still finding the best left number and best right multiplier for each middle position.

A direct triplet scan is far too slow for up to 10^5 elements. The useful rewrite is to treat each j as the center, ask for the maximum nums[i] to its left, ask for the maximum nums[k] to its right, and compute the best product from that split. If every ordered triplet gives a negative result, the final answer must be 0 instead of the largest negative value.

Examples

Example 1

Input: nums = [12,6,1,2,7]

Output: 77

The value of the triplet (0, 2, 4) is (nums[0] - nums[2]) * nums[4] = 77. It can be shown that there are no ordered triplets of indices with a value greater than 77.

Example 2

Input: nums = [1,10,3,4,19]

Output: 133

The value of the triplet (1, 2, 4) is (nums[1] - nums[2]) * nums[4] = 133. It can be shown that there are no ordered triplets of indices with a value greater than 133.

Example 3

Input: nums = [1,2,3]

Output: 0

The only ordered triplet of indices (0, 1, 2) has a negative value of (nums[0] - nums[1]) * nums[2] = -3. Hence, the answer would be 0.

Constraints

3 <= nums.length <= 105
1 <= nums[i] <= 106

Solution Approach

Reframe the triplet around the middle index

The expression depends on three ordered positions, but only j sits between the other two. For each j, the best i is the maximum value seen before j, because a larger left value makes nums[i] - nums[j] larger. The best k is the maximum value after j, because once the difference is fixed, multiplying by the largest right value gives the largest product.

Precompute prefix and suffix maximums

Build a prefix maximum array where prefixMax[j - 1] stores the best nums[i] available to the left of j. Build a suffix maximum array where suffixMax[j + 1] stores the best nums[k] available to the right of j. Then each middle index can be evaluated in O(1) time as (prefixMax[j - 1] - nums[j]) * suffixMax[j + 1], which is the exact array-driven pattern this problem wants.

Scan all valid middle positions and clamp negatives

Iterate j from 1 to n - 2 so both sides exist. Compute the candidate product using the preprocessed left and right maxima, update the running answer, and return max(answer, 0). This final clamp matters because Maximum Value of an Ordered Triplet II explicitly rejects negative triplet values even when every valid ordered triplet is below zero.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The algorithm runs in O(n) time because it builds one prefix maximum array, one suffix maximum array, and then makes one pass over valid middle indices. It uses O(n) extra space for those arrays, although the same idea can be compressed further by keeping a running prefix maximum and a precomputed suffix maximum structure. The important trade-off in this problem is choosing preprocessing over repeated triplet checks, because brute force wastes work on the same left and right comparisons many times.

What Interviewers Usually Probe

They want you to notice that j is the fixed middle and the formula can be split into best left and best right choices.
They expect you to reject O(n^3) triplet enumeration and move to prefix and suffix preprocessing.
They may watch whether you remember the answer is 0 when the best computed product is still negative.

Common Pitfalls or Variants

Common pitfalls

Using the global maximum on the left or right without enforcing i < j < k, which breaks the ordered triplet condition.
Forgetting to clamp the final result to 0, which gives the wrong answer on arrays like [1,2,3].
Computing the product in a type that is too small, since values can exceed 32-bit integer range during multiplication.

Follow-up variants

Replace the right-side maximum with a suffix minimum if the formula changes and the multiplier can benefit from smaller values.
Ask for the indices of the optimal triplet instead of only the value, which means storing where each prefix and suffix maximum came from.
Convert the same ordered-triplet idea into a streaming version where you maintain the best left value and best left-minus-middle score as you scan.

FAQ

What is the main pattern in Maximum Value of an Ordered Triplet II?

The main pattern is prefix and suffix preprocessing around the middle index j. Instead of picking every triplet, you precompute the best left value before j and the best right value after j, then evaluate the formula in constant time per middle position.

Why does checking each middle index j work?

Once j is fixed, the formula becomes independent on each side. You want the largest nums[i] on the left to maximize nums[i] - nums[j], and the largest nums[k] on the right to maximize the final multiplication.

Why is the answer 0 for some arrays even when triplets exist?

The problem says to return 0 if all ordered triplets produce a negative value. That means you still evaluate valid triplets, but you do not return a negative maximum at the end.

Do I need prefix and suffix arrays for this problem?

They are the clearest way to express the solution because they make the ordered constraint explicit and keep each middle-index calculation O(1). In interviews, this is usually the most readable version of the linear-time approach.

What type should I use for the product?

Use 64-bit arithmetic such as long long in C++ or long in Java. Even though each nums value fits in normal integer range, the product of a large difference and a large suffix value can overflow 32-bit integers.

terminal

Solution

Solution 1: Maintaining Prefix Maximum and Maximum Difference

We use two variables $\textit{mx}$ and $\textit{mxDiff}$ to maintain the prefix maximum value and maximum difference, respectively, and use a variable $\textit{ans}$ to maintain the answer. Initially, these variables are all $0$.

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        ans = mx = mx_diff = 0
        for x in nums:
            ans = max(ans, mx_diff * x)
            mx_diff = max(mx_diff, mx - x)
            mx = max(mx, x)
        return ans

Continue Practicing

#2873 maximum value of an ordered triplet i #2875 minimum size subarray in infinite array #2871 split array into maximum number of subarrays