Get started

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

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

  • Difficulty: Medium
  • Topics: Arrays, Math, Prefix Sum
  • Asked at: Amazon, Google, Uber
  • 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 an ordered triplet (i, j, k) with 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: (12 - 1) * 7 = 77.

Example 2

Input: nums = [1,10,3,4,19]
Output: 133
Explanation: (1 - 10) is negative; (10 - 3) * 19 = 133.

Example 3

Input: nums = [1,2,3]
Output: 0
Explanation: The only triplet gives (1 - 2) * 3 = -3, so the answer floors at 0.

Constraints

  • 3 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000000

How to solve Maximum Value of an Ordered Triplet I

Sweep k from left to right while maintaining two running maxima: the largest element seen so far, and the largest difference nums[i] - nums[j] over pairs entirely before k. Then each k is answered in constant time.

Approach

  1. Keep bestI (the maximum element seen), bestDiff (the maximum nums[i] - nums[j] with i < j), and best (the answer, starting at 0).
  2. At index k, first update best with bestDiff * nums[k].
  3. Then update bestDiff with bestI - nums[k], and finally bestI with nums[k].

Why it works

The update order is what enforces i < j < k: bestDiff is read before it is allowed to include index k as a j, and bestI is updated last so it never contributes an i at or after the j that uses it.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Updating bestI before bestDiff lets i and j be the same index.
  • Updating bestDiff before reading it lets j equal k.
  • The answer floors at 0, so it must start at 0 rather than at negative infinity.

Reference solution

Python

from typing import List

def maximumTripletValue(nums: List[int]) -> int:
    best = best_diff = best_i = 0
    for x in nums:
        best = max(best, best_diff * x)
        best_diff = max(best_diff, best_i - x)
        best_i = max(best_i, x)
    return best

JavaScript

var maximumTripletValue = function(nums) {
    var best = 0, bestDiff = 0, bestI = 0;
    for (var k = 0; k < nums.length; k++) {
        if (bestDiff * nums[k] > best) best = bestDiff * nums[k];
        if (bestI - nums[k] > bestDiff) bestDiff = bestI - nums[k];
        if (nums[k] > bestI) bestI = 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