LeetCode Problem 2873

Difficulty: 🟢 Easy
Topics: Array

Solution

LeetCode 2873 - Maximum Value of an Ordered Triplet I

Problem Understanding

You are given an integer array nums and must choose three indices (i, j, k) such that:

• i < j < k
• The triplet value is (nums[i] - nums[j]) * nums[k]

Among all valid ordered triplets, we want the maximum possible value. If every possible triplet produces a negative value, we return 0 instead.

In other words, we need to find three positions that maximize the expression:

$$(nums[i] - nums[j]) \times nums[k]$$

while preserving the ordering constraint i < j < k.

The input array contains positive integers, and its length is between 3 and 100. Since the array is relatively small, even cubic algorithms are technically feasible. However, it is still useful to identify the underlying pattern and derive a more efficient solution.

A few observations are important:

• Since all nums[k] values are positive, maximizing the expression largely depends on maximizing (nums[i] - nums[j]).
• If (nums[i] - nums[j]) is negative, multiplying by a positive nums[k] keeps the result negative.
• The problem explicitly states that if the best value is negative, we should return 0.
• We must respect the ordering requirement, so we cannot freely choose any three values from the array.

Important edge cases include arrays where every increasing pair produces a negative difference, arrays where the maximum value comes from an early large element and a later small element, and arrays containing repeated values that may produce zero-valued triplets.

Approaches

Brute Force

The most direct solution is to enumerate every possible triplet (i, j, k).

For each valid combination:

1. Compute (nums[i] - nums[j]) * nums[k].
2. Track the maximum value seen.
3. Return max(0, answer).

Since there are three nested loops, the time complexity is O(n³).

This approach is correct because it explicitly evaluates every valid triplet and therefore cannot miss the optimal answer. However, it performs unnecessary repeated work because many calculations involve the same prefixes and suffixes.

Key Insight

For a fixed middle index j, the expression can be rewritten as:

$$(\max_{i<j} nums[i] - nums[j]) \times \max_{k>j} nums[k]$$

When j is fixed:

• The best i is simply the largest value appearing before j.
• The best k is simply the largest value appearing after j.

Therefore, instead of checking every triplet, we can:

1. Maintain the maximum value seen to the left of j.
2. Know the maximum value available to the right of j.
3. Compute the candidate value for every possible j.

This reduces the problem to linear processing after some preprocessing.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Tries every valid triplet
Optimal	O(n)	O(n)	Uses prefix maximums and suffix maximums

Algorithm Walkthrough

Optimal Algorithm

1. Create a suffix maximum array suffix_max.

For every index i, store the largest value that appears at or after position i. This allows us to instantly determine the best possible k for any middle position j. 2. Build suffix_max from right to left.

The recurrence is:

suffix_max[i] = max(nums[i], suffix_max[i + 1])

This ensures each position knows the largest value available in its suffix. 3. Initialize left_max as nums[0].

This variable stores the largest value encountered before the current middle index. 4. Iterate through all valid middle indices j.

Since i < j < k, the middle index can range from 1 to n - 2. 5. For each j, compute the best possible triplet value.

The largest valid value before j is left_max.

The largest valid value after j is suffix_max[j + 1].

Therefore:

candidate = (left_max - nums[j]) * suffix_max[j + 1]

6. Update the global answer.

Keep the maximum candidate value seen so far. 7. Update left_max.

After processing j, include nums[j] in the prefix:

left_max = max(left_max, nums[j])

8. Return the answer.

Since the answer starts at 0, negative values are automatically ignored.

Why it works

For every middle position j, the expression depends on two independent choices:

• A value before j, contributing nums[i].
• A value after j, contributing nums[k].

Because nums[k] is always positive, the optimal choice for a fixed j is the largest possible value before j and the largest possible value after j. The algorithm explicitly evaluates this optimal choice for every valid middle index, guaranteeing that the global maximum triplet value is found.

Python Solution

from typing import List

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n = len(nums)

        suffix_max = [0] * n
        suffix_max[-1] = nums[-1]

        for i in range(n - 2, -1, -1):
            suffix_max[i] = max(nums[i], suffix_max[i + 1])

        left_max = nums[0]
        answer = 0

        for j in range(1, n - 1):
            candidate = (left_max - nums[j]) * suffix_max[j + 1]
            answer = max(answer, candidate)

            left_max = max(left_max, nums[j])

        return answer

The implementation begins by constructing the suffix_max array. Each position stores the largest element available from that index to the end of the array.

Next, left_max tracks the largest value encountered before the current middle index. As we scan from left to right, this variable always represents the optimal choice for index i.

For every valid middle index j, we compute the best possible triplet value using the largest value before j and the largest value after j. The answer is updated whenever a larger value is found.

Finally, left_max is updated to include the current element before moving to the next iteration.

Go Solution

func maximumTripletValue(nums []int) int64 {
	n := len(nums)

	suffixMax := make([]int, n)
	suffixMax[n-1] = nums[n-1]

	for i := n - 2; i >= 0; i-- {
		if nums[i] > suffixMax[i+1] {
			suffixMax[i] = nums[i]
		} else {
			suffixMax[i] = suffixMax[i+1]
		}
	}

	leftMax := nums[0]
	var answer int64 = 0

	for j := 1; j < n-1; j++ {
		candidate := int64(leftMax-nums[j]) * int64(suffixMax[j+1])

		if candidate > answer {
			answer = candidate
		}

		if nums[j] > leftMax {
			leftMax = nums[j]
		}
	}

	return answer
}

The Go solution follows exactly the same logic as the Python implementation. One important difference is the use of int64 for the result and intermediate multiplication. Since values can be as large as 10^6, the product may reach approximately 10^12, which exceeds the range of a 32-bit integer. Converting operands to int64 before multiplication avoids overflow.

Worked Examples

Example 1

nums = [12, 6, 1, 2, 7]

Suffix Maximum Array

Index	Value	Suffix Max
0	12	12
1	6	7
2	1	7
3	2	7
4	7	7

Iteration

j	left_max	nums[j]	best right value	candidate	answer
1	12	6	7	(12-6)×7=42	42
2	12	1	7	(12-1)×7=77	77
3	12	2	7	(12-2)×7=70	77

Final answer: 77

Example 2

nums = [1, 10, 3, 4, 19]

Suffix Maximum Array

Index	Value	Suffix Max
0	1	19
1	10	19
2	3	19
3	4	19
4	19	19

Iteration

j	left_max	nums[j]	best right value	candidate	answer
1	1	10	19	-171	0
2	10	3	19	133	133
3	10	4	19	114	133

Final answer: 133

Example 3

nums = [1, 2, 3]

Suffix Maximum Array

Index	Value	Suffix Max
0	1	3
1	2	3
2	3	3

Iteration

j	left_max	nums[j]	best right value	candidate	answer
1	1	2	3	-3	0

Final answer: 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass to build suffix maxima and one pass to evaluate candidates
Space	O(n)	Suffix maximum array stores one value per index

The algorithm performs only two linear scans of the array. Every operation inside those scans is constant time, resulting in overall O(n) time complexity. The extra memory comes solely from the suffix maximum array, which requires O(n) space.

Test Cases

from typing import List

s = Solution()

assert s.maximumTripletValue([12, 6, 1, 2, 7]) == 77      # example 1
assert s.maximumTripletValue([1, 10, 3, 4, 19]) == 133   # example 2
assert s.maximumTripletValue([1, 2, 3]) == 0             # example 3

assert s.maximumTripletValue([5, 5, 5]) == 0             # all equal values
assert s.maximumTripletValue([10, 1, 10]) == 90          # minimum valid length
assert s.maximumTripletValue([100, 1, 1, 100]) == 9900   # large positive difference
assert s.maximumTripletValue([1, 100, 1, 100]) == 9900   # best triplet not starting at index 0
assert s.maximumTripletValue([9, 8, 7, 6]) == 18         # decreasing array
assert s.maximumTripletValue([1, 3, 2, 5]) == 5          # mixed ordering
assert s.maximumTripletValue([1, 2, 1]) == 0             # negative result only
assert s.maximumTripletValue([1000000, 1, 1000000]) == 999999000000  # large values

Test Summary

Test	Why
[12,6,1,2,7]	Validates example 1
[1,10,3,4,19]	Validates example 2
[1,2,3]	Validates negative result handling
[5,5,5]	Ensures equal values produce zero
[10,1,10]	Smallest allowed array length
[100,1,1,100]	Large positive difference case
[1,100,1,100]	Best prefix maximum appears later
[9,8,7,6]	Decreasing sequence
[1,3,2,5]	General mixed values
[1,2,1]	Only negative candidate exists
[1000000,1,1000000]	Verifies large-number arithmetic

Edge Cases

All Triplets Produce Negative Values

Consider:

[1, 2, 3]

The only triplet produces (1 - 2) * 3 = -3. A common bug is returning the largest computed value directly, which would incorrectly return -3. This implementation initializes the answer to 0, ensuring negative values are ignored automatically.

Repeated Values

Consider:

[5, 5, 5]

Every triplet produces (5 - 5) * 5 = 0. Some implementations incorrectly assume a positive difference must exist. Our solution correctly computes the candidate value and allows zero to remain the maximum.

Very Large Numbers

Consider:

[1000000, 1, 1000000]

The result is:

(1000000 - 1) * 1000000 = 999999000000

This exceeds the range of a 32-bit integer. The Go implementation explicitly uses int64 for multiplication and storage of the answer, preventing overflow.

Best Prefix Maximum Appears Before the Current Middle Index

Consider:

[1, 100, 1, 100]

The optimal triplet uses the value 100 at index 1 as the left element. Maintaining left_max ensures that for every middle index, we always know the largest value available before it. This guarantees that the optimal i is considered without checking every previous position.