Maximum Value of an Ordered Triplet II — Problem & Solution
Maximum Value of an Ordered Triplet II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Value of an Ordered Triplet II is a medium coding problem on arrays and prefix sum, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Prefix Sum
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The value of the ordered triplet i < j < k is (nums[i] - nums[j]) * nums[k].
Return the maximum value over all such triplets, or 0 if every triplet has a negative value.
Example 1
Input: nums = [12,6,1,2,7]
Output: 77
Explanation: Indices 0, 2 and 4: `(12 - 1) × 7`.
Example 2
Input: nums = [1,10,3,4,19]
Output: 133
Explanation: Indices 1, 2 and 4: `(10 - 3) × 19`.
Example 3
Input: nums = [1,2,3]
Output: 0
Explanation: The only triplet is negative.
Constraints
3 <= nums.length <= 10^51 <= nums[i] <= 10^4
Hints for Maximum Value of an Ordered Triplet II
Hint 1
Sweep
kfrom left to right and keep the best(nums[i] - nums[j])seen so far.Hint 2
That in turn needs the largest
nums[i]seen before the currentj.Hint 3
Two running maxima are enough — no nested loops.
How to solve Maximum Value of an Ordered Triplet II
One pass, carrying two running values: the largest element seen so far, and the largest difference nums[i] - nums[j] over pairs seen so far. At each k the answer candidate is maxDiff × nums[k].
Approach
- Sweep
kfrom left to right. - Score
maxDiff × nums[k]against the best so far. - Update
maxDiffwithmaxI - nums[k], treating the current element as aj. - Update
maxIwithnums[k], treating it as ani.
Why it works
The update order is the whole trick: scoring before the updates guarantees the i and j behind maxDiff both lie strictly before k. Because all values are positive, a negative maxDiff can never beat the initial 0, which is exactly the fallback the statement asks for.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Updating the running maxima before scoring lets
kbe used as its owniorj. - The answer is clamped at 0, so a wholly negative array answers 0.
- The products reach
10^4 × 10^4 = 10^8, which fits an int but not with much room.
Reference solution
Python
from typing import List
def maximumTripletValue(nums: List[int]) -> int:
best = 0
max_i = 0
max_diff = 0
for v in nums:
best = max(best, max_diff * v)
max_diff = max(max_diff, max_i - v)
max_i = max(max_i, v)
return bestJava
public static int maximumTripletValue(int[] nums) {
long best = 0;
long maxI = 0, maxDiff = 0;
for (int v : nums) {
best = Math.max(best, maxDiff * v);
maxDiff = Math.max(maxDiff, maxI - v);
maxI = Math.max(maxI, v);
}
return (int) best;
}C++
int maximumTripletValue(vector<int>& nums) {
long long best = 0, maxI = 0, maxDiff = 0;
for (int v : nums) {
best = max(best, maxDiff * v);
maxDiff = max(maxDiff, maxI - v);
maxI = max(maxI, (long long) v);
}
return (int) best;
}JavaScript
var maximumTripletValue = function(nums) {
var best = 0, maxI = 0, maxDiff = 0;
for (var k = 0; k < nums.length; k++) {
var v = maxDiff * nums[k];
if (v > best) best = v;
if (maxI - nums[k] > maxDiff) maxDiff = maxI - nums[k];
if (nums[k] > maxI) maxI = nums[k];
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Prefix Sum