Get started

Maximum Value of an Ordered Triplet II — Medium Problem & Solution

The value of the ordered triplet i < j < k is (nums[i] - nums[j]) * nums[k].

  • 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

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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue