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 I

Number: 3154

Difficulty: Easy

Paid? No

Companies: Google, Media.net

Problem Description

Given a 0-indexed integer array nums, find the maximum value of any ordered triplet (i, j, k) with i < j < k where the value is defined by (nums[i] - nums[j]) * nums[k]. If every triplet yields a negative value, return 0.

Key Insights

  • The triplet value (nums[i] - nums[j]) * nums[k] is only positive when nums[i] > nums[j] and nums[k] is large.
  • Using three nested loops (i, j, k) is acceptable for n ≤ 100, though optimization is possible.
  • Alternatively, for each middle index j, one can track the maximum element before j (to maximize nums[i] - nums[j]) and the maximum element after j (to maximize nums[k]).
  • By precomputing a prefix maximum and suffix maximum, the problem reduces to iterating over j and computing: candidate = (prefix_max[j-1] - nums[j]) * suffix_max[j+1] and taking the maximum candidate.

Space and Time Complexity

Time Complexity: O(n) when using prefix and suffix arrays (with two passes plus one pass for evaluation).
Space Complexity: O(n) for maintaining the prefix and suffix arrays.

Solution

We can optimize the solution by computing two auxiliary arrays: one for the prefix maximum (max value before the current index) and one for the suffix maximum (max value after the current index).

  1. Create a prefix_max array so that for each index j, prefix_max[j] holds the maximum number from index 0 to j.
  2. Create a suffix_max array so that for each index j, suffix_max[j] holds the maximum number from j to the end of the array.
  3. Then, iterate over the possible middle elements (j from 1 to n-2) and compute:
    candidate = (prefix_max[j-1] - nums[j]) * suffix_max[j+1]
  4. Track the maximum candidate over all valid j. Return the maximum candidate if it is more than 0; otherwise, return 0.

Code Solutions

# Python solution with line-by-line comments
def maximumTripletValue(nums):
    n = len(nums)
    # Initialize prefix and suffix maximum arrays
    prefix_max = [0] * n  # prefix_max[i] will store the maximum from nums[0] to nums[i]
    suffix_max = [0] * n  # suffix_max[i] will store the maximum from nums[i] to nums[n-1]
    
    # Build prefix maximum array
    prefix_max[0] = nums[0]
    for i in range(1, n):
        prefix_max[i] = max(prefix_max[i-1], nums[i])
        
    # Build suffix maximum array
    suffix_max[-1] = nums[-1]
    for i in range(n-2, -1, -1):
        suffix_max[i] = max(suffix_max[i+1], nums[i])
    
    max_value = 0  # Initialize result as 0 (since negative results are not accepted)
    
    # Iterate over all possible middle indices j (must have at least one element before and after)
    for j in range(1, n-1):
        # Only valid if there is an element before j making the difference positive.
        current_diff = prefix_max[j-1] - nums[j]
        candidate = current_diff * suffix_max[j+1]
        max_value = max(max_value, candidate)
    
    return max_value

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