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 is calculated using the formula: (nums[i] - nums[j]) * nums[k].

The goal is to return the maximum value that can be obtained from any valid triplet. If all possible triplets produce negative values, return 0.

For example, if you have indices i, j, and k with i < j < k, you would:

1. Take the element at index i: nums[i]
2. Subtract the element at index j: nums[i] - nums[j]
3. Multiply the result by the element at index k: (nums[i] - nums[j]) * nums[k]

You need to find which combination of three indices gives you the largest possible value according to this formula.

Intuition

To find the maximum value of (nums[i] - nums[j]) * nums[k] where i < j < k, let's think about what we need at each position.

When we're at position k, we want to maximize (nums[i] - nums[j]) * nums[k] for all valid i and j before k. If nums[k] is positive, we want the maximum possible value of (nums[i] - nums[j]). If nums[k] is negative, we'd want the minimum value of (nums[i] - nums[j]), but since we're looking for the maximum triplet value and can return 0 if all values are negative, we can focus on maximizing (nums[i] - nums[j]).

Now, how do we maximize (nums[i] - nums[j]) for positions before k? We need the largest nums[i] and the smallest nums[j] where i < j. But there's a constraint: i must come before j.

The key insight is that as we iterate through the array, we can maintain:

1. The maximum value seen so far (this could be a potential nums[i])
2. The maximum difference (nums[i] - nums[j]) seen so far using valid pairs

When we reach a new element, it can play three roles:

• It can be nums[k] for all previous valid (i, j) pairs
• It can be nums[j] paired with all previous maximum values as nums[i]
• It can be a future nums[i] for upcoming elements

This suggests a single-pass solution where we maintain the maximum element seen and the maximum difference seen, updating our answer as we process each element as a potential nums[k].

Solution Approach

We implement a single-pass solution using three variables to track the necessary information as we iterate through the array:

1. ans: Maintains the maximum triplet value found so far
2. mx: Tracks the maximum element seen up to the current position (potential nums[i])
3. mx_diff: Stores the maximum difference (nums[i] - nums[j]) for all valid pairs before the current position

The algorithm processes each element x in the array as a potential nums[k]:

Step-by-step process for each element x:

1. Calculate triplet value: First, we compute mx_diff * x. This gives us the maximum possible triplet value when x serves as nums[k], using the best (nums[i] - nums[j]) pair found before this position. We update ans = max(ans, mx_diff * x).

2. Update maximum difference: Next, we calculate mx - x. This represents a new potential difference where mx (the largest element seen so far) acts as nums[i] and the current element x acts as nums[j]. We update mx_diff = max(mx_diff, mx - x) to maintain the best difference for future elements.

3. Update maximum element: Finally, we update mx = max(mx, x) to ensure we always have the largest element seen so far, which could serve as nums[i] for future pairs.

The order of these updates is crucial:

• We must calculate the answer before updating mx_diff because x is acting as nums[k] and needs the differences from strictly earlier pairs
• We must update mx_diff before updating mx because we need the old maximum to calculate the new difference with x as nums[j]

After processing all elements, we return ans, which automatically handles the case where all triplets are negative (since ans starts at 0).

Example Walkthrough

Let's walk through the solution with the array nums = [3, 1, 5, 2, 4].

We initialize:

• ans = 0 (maximum triplet value found)
• mx = 3 (first element)
• mx_diff = 0 (no valid difference yet)

Processing index 1 (x = 1):

• Calculate triplet value: mx_diff * x = 0 * 1 = 0, so ans = max(0, 0) = 0
• Update max difference: mx - x = 3 - 1 = 2, so mx_diff = max(0, 2) = 2
  • This means we now have a valid pair where nums[0]=3 is i and nums[1]=1 is j
• Update max element: mx = max(3, 1) = 3

Processing index 2 (x = 5):

• Calculate triplet value: mx_diff * x = 2 * 5 = 10, so ans = max(0, 10) = 10
  • This represents the triplet (0,1,2) with value (3-1)*5 = 10
• Update max difference: mx - x = 3 - 5 = -2, so mx_diff = max(2, -2) = 2
• Update max element: mx = max(3, 5) = 5

Processing index 3 (x = 2):

• Calculate triplet value: mx_diff * x = 2 * 2 = 4, so ans = max(10, 4) = 10
• Update max difference: mx - x = 5 - 2 = 3, so mx_diff = max(2, 3) = 3
  • Now our best difference is from pair (2,3) where nums[2]=5 is i and nums[3]=2 is j
• Update max element: mx = max(5, 2) = 5

Processing index 4 (x = 4):

• Calculate triplet value: mx_diff * x = 3 * 4 = 12, so ans = max(10, 12) = 12
  • This represents the triplet (2,3,4) with value (5-2)*4 = 12
• Update max difference: mx - x = 5 - 4 = 1, so mx_diff = max(3, 1) = 3
• Update max element: mx = max(5, 4) = 5

The maximum triplet value is 12, achieved by indices (2,3,4) with calculation (nums[2] - nums[3]) * nums[4] = (5 - 2) * 4 = 12.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs a single pass through the input array nums of length n. In each iteration, it performs only constant-time operations:

• Three max() comparisons with fixed number of arguments
• One multiplication operation
• Variable updates

Since we iterate through each element exactly once and perform O(1) operations per element, the overall time complexity is O(n).

Space Complexity: O(1)

The algorithm uses only a fixed amount of extra space regardless of input size:

• Three integer variables: ans, mx, and mx_diff
• One loop variable: x

These variables do not scale with the input size n, so the space complexity is constant, O(1).

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

Common Pitfalls

Pitfall 1: Incorrect Update Order

The Problem: A common mistake is updating the variables in the wrong order within the loop. For example:

# WRONG ORDER - This will produce incorrect results
for current_num in nums:
    max_element = max(max_element, current_num)  # Updated too early!
    max_difference = max(max_difference, max_element - current_num)
    max_triplet_value = max(max_triplet_value, max_difference * current_num)

When you update max_element first, you're including the current element in the calculation of max_difference, which violates the constraint that i < j. The current element cannot simultaneously be both nums[i] and nums[j].

The Solution: Always maintain the correct update sequence:

1. First calculate the triplet value (current element as nums[k])
2. Then update the maximum difference (current element as nums[j])
3. Finally update the maximum element (current element as potential future nums[i])

Pitfall 2: Using Insufficient Initial Values

The Problem: Initializing tracking variables with values that are too small can cause issues with negative numbers:

# WRONG - May miss valid negative differences
max_element = 0  
max_difference = 0

If the array starts with negative numbers like [-5, -3, 2, 8], initializing max_element to 0 means we'd miss the valid difference of (-5) - (-3) = -2 in early iterations.

The Solution: Two approaches work:

1. Initialize with the first element: max_element = nums[0] (requires checking array length)
2. Use negative infinity: max_element = float('-inf') to ensure all actual values are considered

Pitfall 3: Misunderstanding Variable Roles

The Problem: Confusing what each variable represents at different points in the iteration:

# Conceptual error - thinking max_difference can use current element
for current_num in nums:
    # WRONG thinking: "I can use current_num in max_difference calculation"
    max_triplet_value = max(max_triplet_value, (current_num - something) * something_else)

The Solution: Remember the temporal relationship:

• When processing element at index k, max_difference contains the best (nums[i] - nums[j]) where both i and j are strictly less than k
• The current element can only play one role per iteration: it's nums[k] for the answer calculation, then becomes a potential nums[j] for difference calculation, and finally a potential nums[i] for future iterations

Pitfall 4: Off-by-One Errors with Index Constraints

The Problem: Attempting to manually track indices and making errors with the strict inequality requirements:

# WRONG - Trying to manually ensure i < j < k with complex logic
if current_index > 1:  # Ensuring at least 3 elements
    if previous_index < current_index - 1:  # Complex and error-prone
        # calculate...

The Solution: The beauty of this algorithm is that it implicitly maintains the ordering constraint through the update sequence. By updating variables in the correct order, you automatically ensure that:

• max_element comes from indices before the current j
• max_difference comes from pairs before the current k
• No explicit index tracking is needed