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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Value of an Ordered Triplet II

Difficulty: Medium

Problem Description

You are given a 0-indexed integer array nums. Return the maximum value over all triplets of indices (i, j, k) such that i < j < k. If all such triplets have a negative value, return 0. The value of a triplet of indices (i, j, k) is equal to (nums[i] - nums[j]) * nums[k].

Key Insights

  • The problem requires evaluating multiple triplet combinations while adhering to the index constraints.
  • The value of each triplet depends on the difference between the first two elements multiplied by the third element.
  • The solution should efficiently compute the maximum value without explicitly generating all possible triplets due to the potential size of the input.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)

Solution

To solve the problem, we can iterate through the array to find potential triplets (i, j, k). For each element at index j, we can compute the maximum value of nums[i] for indices i < j and the maximum value of nums[k] for indices k > j. This way, we can efficiently calculate the value of the triplet (i, j, k) without needing to check every combination.

  1. Create two auxiliary arrays: maxLeft and maxRight.
  2. Populate maxLeft such that maxLeft[j] is the maximum value of nums[i] for all i < j.
  3. Populate maxRight such that maxRight[j] is the maximum value of nums[k] for all k > j.
  4. For each index j, calculate the triplet value using the formula (maxLeft[j] - nums[j]) * maxRight[j].
  5. Track the maximum value found and return it, ensuring to return 0 if the maximum is negative.

Code Solutions

def maxTripletValue(nums):
    n = len(nums)
    if n < 3:
        return 0

    maxLeft = [0] * n
    maxRight = [0] * n

    # Fill maxLeft
    maxLeft[0] = nums[0]
    for j in range(1, n):
        maxLeft[j] = max(maxLeft[j - 1], nums[j - 1])

    # Fill maxRight
    maxRight[n - 1] = nums[n - 1]
    for j in range(n - 2, -1, -1):
        maxRight[j] = max(maxRight[j + 1], nums[j + 1])

    maxValue = float('-inf')
    for j in range(1, n - 1):
        value = (maxLeft[j] - nums[j]) * maxRight[j]
        maxValue = max(maxValue, value)

    return max(0, maxValue)
← Back to All Questions