Maximum Value of an Ordered Triplet I

Difficulty: Easy | Acceptance: 58.20% | Paid: No Topics: Array

You are given a 0-indexed integer array nums of length n.

Return the maximum value of (nums[i] - nums[j]) * nums[k] such that 0 <= i < j < k < n.

• Examples
• Constraints
• Brute Force
• Prefix and Suffix Maximum
• Single Pass Optimization

Examples

Example 1:

Input: nums = [12,6,1,2,7]
Output: 77
Explanation: The triplet (2, 1, 4) has a maximum value of (12 - 1) * 7 = 77.

Example 2:

Input: nums = [1,10,3,4,19]
Output: 133
Explanation: The triplet (1, 2, 4) has a maximum value of (10 - 3) * 19 = 133.

Example 3:

Input: nums = [1,2,3]
Output: 0
Explanation: The triplet (0, 1, 2) has a value of (1 - 2) * 3 = -3, but the maximum value is 0.

Constraints

3 <= nums.length <= 100
1 <= nums[i] <= 10^6

Brute Force

Intuition Try all possible triplets (i, j, k) where i < j < k and compute the value for each, keeping track of the maximum.

Steps

• Iterate through all valid combinations of i, j, k with i < j < k
• Calculate (nums[i] - nums[j]) * nums[k] for each triplet
• Track and return the maximum value found

from typing import List

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n = len(nums)
        max_val = float('-inf')
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    val = (nums[i] - nums[j]) * nums[k]
                    max_val = max(max_val, val)
        return max(0, max_val)

Complexity

• Time: O(n³)
• Space: O(1)
• Notes: Simple but inefficient for larger arrays

Prefix and Suffix Maximum

Intuition For each index j, we need the maximum nums[i] to its left and maximum nums[k] to its right. Precompute these using prefix and suffix arrays.

Steps

• Build prefix_max array where prefix_max[i] = max(nums[0..i])
• Build suffix_max array where suffix_max[i] = max(nums[i..n-1])
• For each j from 1 to n-2, compute (prefix_max[j-1] - nums[j]) * suffix_max[j+1]
• Return the maximum value found

from typing import List

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n = len(nums)
        prefix_max = [0] * n
        suffix_max = [0] * n
        
        prefix_max[0] = nums[0]
        for i in range(1, n):
            prefix_max[i] = max(prefix_max[i-1], nums[i])
        
        suffix_max[n-1] = nums[n-1]
        for i in range(n-2, -1, -1):
            suffix_max[i] = max(suffix_max[i+1], nums[i])
        
        max_val = float('-inf')
        for j in range(1, n-1):
            val = (prefix_max[j-1] - nums[j]) * suffix_max[j+1]
            max_val = max(max_val, val)
        
        return max(0, max_val)

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Uses extra space for prefix and suffix arrays

Single Pass Optimization

Intuition Track the maximum value seen so far (for nums[i]) and the maximum difference (nums[i] - nums[j]) seen so far as we iterate through the array.

Steps

• Initialize max_left to nums[0], max_diff to negative infinity, and result to negative infinity
• For each position j from 1 to n-1:
  • If j >= 2, update result using max_diff * nums[j]
  • Update max_diff with (max_left - nums[j])
  • Update max_left with nums[j]
• Return the maximum of 0 and result

from typing import List

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n = len(nums)
        max_left = nums[0]
        max_diff = float('-inf')
        result = float('-inf')
        
        for j in range(1, n):
            if j >= 2:
                result = max(result, max_diff * nums[j])
            max_diff = max(max_diff, max_left - nums[j])
            max_left = max(max_left, nums[j])
        
        return max(0, result)

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Optimal solution with constant extra space