We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Value of an Ordered Triplet II

Number: 3152

Difficulty: Medium

Paid? No

Companies: Google, Bloomberg, Media.net

Problem Description

Given a 0-indexed integer array nums, we need to find the maximum value among all triplets (i, j, k) such that i < j < k, where the value of a triplet is defined as (nums[i] - nums[j]) * nums[k]. If every possible triplet yields a negative value, return 0.

Key Insights

  • The order i < j < k forces us to consider elements to the left and right of a chosen middle element j.
  • For any fixed middle element nums[j], the best candidate for nums[i] is the maximum element to its left (to maximize nums[i] - nums[j]).
  • Similarly, the best candidate for nums[k] is the maximum element to its right.
  • Precomputing the maximum value on the right side for each element (using a suffix maximum) can help efficiently evaluate each potential middle index.
  • The overall maximum is the best value from (leftMax - nums[j]) * rightMax for each valid j; if negative, the answer should be 0.

Space and Time Complexity

Time Complexity: O(n) – We traverse the array to compute the suffix maximum and then another pass to compute the best triplet value. Space Complexity: O(n) – Additional space is used for the suffix maximum array, though it can sometimes be optimized to O(1) with a reverse traversal.

Solution

We approach the problem by iterating through the array while keeping track of the maximum value seen so far from the left (for potential nums[i]). Meanwhile, we precompute a suffix array rightMax where for each index j, rightMax[j] contains the maximum value found in nums from index j+1 to the end (for potential nums[k]). For each index j (acting as the middle element), we compute the candidate value as (leftMax - nums[j]) * rightMax[j] and update the maximum result. Finally, we return 0 if the computed maximum is negative.

Code Solutions

# Python solution for Maximum Value of an Ordered Triplet II

def maximumTripletValue(nums):
    n = len(nums)
    # Create a suffix array to store the maximum element to the right for each index
    rightMax = [0] * n
    rightMax[n - 1] = nums[n - 1]
    
    # Build the suffix maximum array from right to left
    for i in range(n - 2, -1, -1):
        rightMax[i] = max(nums[i], rightMax[i + 1])
    
    max_value = float("-inf")
    leftMax = nums[0]  # maximum element on the left side
    
    # Iterate through the array, treating each index as the middle element
    for j in range(1, n - 1):
        # Update left maximum up to index j-1
        leftMax = max(leftMax, nums[j - 1])
        current_value = (leftMax - nums[j]) * rightMax[j + 1]
        max_value = max(max_value, current_value)
    
    return max_value if max_value > 0 else 0

# Example usage:
print(maximumTripletValue([12, 6, 1, 2, 7]))  # Output: 77
← Back to All Questions