Problem Description

You are given a 0-indexed integer array nums.

Your task is to find the maximum value among all possible triplets of indices (i, j, k) where i < j < k. The value of a triplet (i, j, k) is calculated as (nums[i] - nums[j]) * nums[k].

If all possible triplets result in a negative value, you should return 0.

The key insight is that for each position k, you want to maximize (nums[i] - nums[j]) * nums[k] where i < j < k. This can be done efficiently by tracking:

• The maximum value seen so far (which could be nums[i])
• The maximum difference nums[i] - nums[j] seen so far for valid i < j

As you iterate through the array, each element can play the role of nums[k], and you can use the previously computed maximum difference to calculate potential triplet values. The solution maintains these values in a single pass through the array, updating the maximum triplet value, the maximum difference, and the maximum element as it progresses.

Intuition

To maximize (nums[i] - nums[j]) * nums[k] where i < j < k, let's think about what we need when we're at position k.

At any position k, we want to multiply nums[k] with the largest possible value of (nums[i] - nums[j]) where both i and j come before k. This means we need to track the maximum difference we've seen so far.

But how do we maintain the maximum difference (nums[i] - nums[j]) efficiently? For this difference to be large, we want nums[i] to be as large as possible and nums[j] to be as small as possible, with i < j.

Here's the key realization: as we iterate through the array, each element can play different roles:

• When we see element at position k, it can be used as the third element nums[k] in our triplet
• The same element can also be used as nums[j] (the middle element) for future triplets
• It can also potentially be nums[i] (the first element) for even later triplets

This suggests we can solve the problem in a single pass by maintaining:

1. The maximum value seen so far (this could serve as nums[i])
2. The maximum difference nums[i] - nums[j] seen so far (where i < j)
3. The maximum triplet value found so far

As we move through the array, for each element x:

• First, we try using x as nums[k] and multiply it with the best (nums[i] - nums[j]) we've found
• Then, we update our maximum difference by considering x as a potential nums[j] with the best nums[i] we've seen
• Finally, we update our maximum value by considering x as a potential future nums[i]

This ordering is crucial - we must update in this sequence to ensure we're only using valid indices where i < j < k.

Solution Approach

The solution uses a single-pass algorithm with three variables to track the necessary values:

1. ans: Maintains the maximum triplet value found so far
2. mx_diff: Tracks the maximum difference (nums[i] - nums[j]) where i < j
3. mx: Stores the maximum value seen so far in the array

The algorithm iterates through each element x in the array, treating it as nums[k]:

Step 1: Update the answer

ans = max(ans, mx_diff * x)

At this point, mx_diff contains the best (nums[i] - nums[j]) from all valid pairs before the current position. We multiply it by the current element x (acting as nums[k]) to get a potential triplet value and update our answer if this value is larger.

Step 2: Update the maximum difference

mx_diff = max(mx_diff, mx - x)

Now we consider x as a potential nums[j] for future triplets. We calculate mx - x where mx is the largest element seen before x (potential nums[i]). This gives us a new difference that might be used with future elements as nums[k].

Step 3: Update the maximum value

mx = max(mx, x)

Finally, we update mx to include the current element x, as it could serve as nums[i] for future triplets.

Why this order matters:

• We must calculate the triplet value before updating mx_diff to ensure we're using differences from strictly earlier positions
• We must update mx_diff before updating mx to ensure the difference is calculated with elements where i < j
• This ordering naturally maintains the constraint i < j < k

The algorithm returns ans after processing all elements. If all triplets are negative, ans remains 0 (its initial value), which is the correct output for that case.

Time Complexity: O(n) - single pass through the array
Space Complexity: O(1) - only using a constant amount of extra space

Example Walkthrough

Let's walk through the solution with nums = [10, 13, 5, 18].

We want to find the maximum value of (nums[i] - nums[j]) * nums[k] where i < j < k.

Initial state:

• ans = 0 (maximum triplet value)
• mx_diff = 0 (maximum difference)
• mx = 0 (maximum value seen)

Iteration 1: x = 10 (index 0)

• Calculate triplet: ans = max(0, 0 * 10) = 0
  • No valid triplet yet (need at least 3 elements)
• Update difference: mx_diff = max(0, 0 - 10) = 0
  • Can't form a valid difference yet
• Update max: mx = max(0, 10) = 10
  • 10 could be nums[i] for future triplets

Iteration 2: x = 13 (index 1)

• Calculate triplet: ans = max(0, 0 * 13) = 0
  • Still no valid triplet (need i < j < k)
• Update difference: mx_diff = max(0, 10 - 13) = 0
  • Difference is negative, keep 0
• Update max: mx = max(10, 13) = 13
  • 13 is now the largest potential nums[i]

Iteration 3: x = 5 (index 2)

• Calculate triplet: ans = max(0, 0 * 5) = 0
  • Using x=5 as nums[k], but mx_diff is still 0
• Update difference: mx_diff = max(0, 13 - 5) = 8
  • Now we have a valid difference! (13 at index 1) - (5 at index 2) = 8
• Update max: mx = max(13, 5) = 13
  • 13 remains the largest

Iteration 4: x = 18 (index 3)

• Calculate triplet: ans = max(0, 8 * 18) = 144
  • Using x=18 as nums[k] and mx_diff=8 from (13-5)
  • This represents the triplet (1, 2, 3): (13 - 5) * 18 = 144
• Update difference: mx_diff = max(8, 13 - 18) = 8
  • Keep the better difference of 8
• Update max: mx = max(13, 18) = 18
  • 18 is now the largest

Result: Return ans = 144

The maximum triplet value is 144, coming from indices (1, 2, 3) where:

• i = 1: nums[1] = 13
• j = 2: nums[2] = 5
• k = 3: nums[3] = 18
• Value: (13 - 5) * 18 = 8 * 18 = 144

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. The algorithm iterates through the array exactly once with a single for loop, performing a constant number of operations (comparisons and assignments) for each element.

The space complexity is O(1). The algorithm only uses three auxiliary variables (ans, mx, and mx_diff) to track the maximum values throughout the iteration, regardless of the input size. No additional data structures that scale with input size are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Variable Update Order

One of the most common mistakes is updating the tracking variables in the wrong order. Consider this incorrect implementation:

# WRONG ORDER!
for current_num in nums:
    max_value_seen = max(max_value_seen, current_num)  # Updated too early!
    max_difference = max(max_difference, max_value_seen - current_num)
    max_triplet_value = max(max_triplet_value, max_difference * current_num)

Why this fails: By updating max_value_seen before calculating the difference, we're allowing current_num to be both nums[i] and nums[j] in the same iteration. This violates the constraint that i < j < k and can produce incorrect results.

Example where it fails:

• Input: [5, 6, 7]
• At index 1 (value 6):
  • Wrong order would update max_value_seen to 6 first
  • Then calculate difference as 6 - 6 = 0
  • Missing the valid difference 5 - 6 = -1

Pitfall 2: Not Handling Zero or Negative Results

Another mistake is assuming the answer must be positive and initializing variables incorrectly:

# WRONG INITIALIZATION!
max_triplet_value = float('-inf')  # Should be 0
max_difference = float('-inf')     # Should be 0

Why this fails: The problem states that if all triplets are negative, we should return 0. By initializing to negative infinity, we might return a negative value instead of 0.

Pitfall 3: Misunderstanding the Roles of Variables

Developers might confuse what each variable represents at different points in the iteration:

# CONCEPTUAL ERROR!
for k, current_num in enumerate(nums):
    # Trying to use current_num as nums[i] when it should be nums[k]
    max_difference = max(max_difference, current_num - max_value_seen)  # WRONG!

Solution to Avoid These Pitfalls:

1. Maintain strict update order: Always update in the sequence: answer → difference → maximum value
2. Initialize to zero: Start with max_triplet_value = 0, max_difference = 0, and max_value_seen = 0
3. Clear variable naming: Use descriptive names that indicate the role of each variable
4. Add comments: Document what each variable represents and why the update order matters

Correct implementation pattern:

def maximumTripletValue(self, nums: List[int]) -> int:
    ans = 0        # Maximum triplet value (return 0 if all negative)
    mx_diff = 0    # Best (nums[i] - nums[j]) where i < j
    mx = 0         # Maximum value seen so far
  
    for x in nums:
        # x is nums[k] for this calculation
        ans = max(ans, mx_diff * x)
      
        # x becomes nums[j] for future iterations
        mx_diff = max(mx_diff, mx - x)
      
        # x becomes potential nums[i] for future iterations
        mx = max(mx, x)
  
    return ans