Maximum Value of an Ordered Triplet II

Medium
989.

Maximum Value of an Ordered Triplet II

Maximum Value of an Ordered Triplet II is a medium coding problem on arrays and prefix sum, asked in Amazon, Google and Microsoft interviews.

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^5
  • 1 <= nums[i] <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumTripletValue = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • 1 <= nums[i] <= 10^4

Hints for Maximum Value of an Ordered Triplet II

  1. Hint 1

    Sweep k from left to right and keep the best (nums[i] - nums[j]) seen so far.

  2. Hint 2

    That in turn needs the largest nums[i] seen before the current j.

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

  1. Sweep k from left to right.
  2. Score maxDiff × nums[k] against the best so far.
  3. Update maxDiff with maxI - nums[k], treating the current element as a j.
  4. Update maxI with nums[k], treating it as an i.

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 k be used as its own i or j.
  • 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 best

Java

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