LeetCode 2874 - Maximum Value of an Ordered Triplet II
The problem gives us a 0-indexed integer array nums and asks us to find the maximum possible value of: subject to the constraint: In other words, we must choose three indices in increasing order.
Difficulty: 🟡 Medium
Topics: Array
Solution
LeetCode 2874 - Maximum Value of an Ordered Triplet II
Problem Understanding
The problem gives us a 0-indexed integer array nums and asks us to find the maximum possible value of:
$$(nums[i] - nums[j]) \times nums[k]$$
subject to the constraint:
$$i < j < k$$
In other words, we must choose three indices in increasing order. The first element contributes positively, the second element is subtracted from the first, and the resulting difference is multiplied by the third element.
Our goal is to examine all valid ordered triplets and return the largest value obtainable. If every possible triplet produces a negative value, we return 0 instead.
The input array can contain up to 10^5 elements, and each value can be as large as 10^6.
These constraints are important because they immediately rule out brute-force enumeration of all triplets. A naive solution would require checking every combination of (i, j, k), which would be far too slow.
Another important observation is that the result can become quite large:
$$(10^6 - 1) \times 10^6 \approx 10^{12}$$
Therefore, 64-bit integers are required. Python handles this automatically, while Go must use int64.
Several edge cases deserve attention:
- Arrays where every valid triplet produces a negative value.
- Arrays with only three elements, where there is exactly one possible triplet.
- Cases where the optimal triplet uses elements that are far apart.
- Cases where a large value of
nums[k]compensates for a smaller difference(nums[i] - nums[j]).
The problem guarantees that nums.length >= 3, so at least one valid triplet always exists.
Approaches
Brute Force
The most direct solution is to generate every possible ordered triplet (i, j, k) satisfying i < j < k.
For each triplet, compute:
$$(nums[i] - nums[j]) \times nums[k]$$
and keep track of the maximum value encountered.
This approach is correct because it explicitly evaluates every valid candidate. Since the answer must come from one of these triplets, the maximum value found is guaranteed to be the correct answer.
However, the number of triplets is:
$$O(n^3)$$
With n = 10^5, this is completely infeasible.
Key Insight
Rewrite the expression as:
$$(nums[i] - nums[j]) \times nums[k]$$
Suppose we fix the middle position j.
For that fixed j, the best possible i is simply the largest value appearing before j, because larger nums[i] always increases:
$$nums[i] - nums[j]$$
Similarly, the best possible k is the largest value appearing after j, because larger nums[k] always increases the final product whenever the difference is positive.
Therefore, for every position j, we only need:
- Maximum value to the left of
j - Maximum value to the right of
j
Then the best triplet using that j is:
$$(\text{maxLeft}[j] - nums[j]) \times \text{maxRight}[j]$$
We can precompute suffix maximums and maintain prefix maximums while scanning the array.
This reduces the problem to a linear-time solution.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n³) | O(1) | Checks every ordered triplet |
| Optimal | O(n) | O(n) | Uses prefix and suffix maximum values |
Algorithm Walkthrough
Step 1
Create a suffix maximum array.
For every position i, store the largest value appearing in the range [i, n-1].
This allows us to instantly know the largest possible nums[k] for any middle index j.
Step 2
Initialize a variable max_left with nums[0].
This will always represent the largest value seen before the current position.
Step 3
Iterate through every valid middle index j.
Since i < j < k, the middle index must satisfy:
1 <= j <= n - 2
Step 4
For the current j, retrieve:
best_left = max_left
best_right = suffix_max[j + 1]
These are the largest values available on each side of j.
Step 5
Compute:
candidate = (best_left - nums[j]) * best_right
This is the largest possible triplet value that uses the current middle index.
Update the answer if this candidate is larger.
Step 6
Update max_left:
max_left = max(max_left, nums[j])
This ensures that future positions have access to the largest value seen so far.
Step 7
After processing all middle positions, return:
max(answer, 0)
because the problem requires returning 0 when every triplet value is negative.
Why it works
For a fixed middle index j, the expression depends on two independent choices:
$$(nums[i] - nums[j]) \times nums[k]$$
To maximize the difference term, we should choose the largest possible value before j.
To maximize the multiplier, we should choose the largest possible value after j.
Because these choices are independent, the optimal triplet for each j is fully determined by the maximum element on its left and the maximum element on its right. Evaluating this for every possible middle position guarantees that the global optimum 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])
max_left = nums[0]
answer = 0
for j in range(1, n - 1):
candidate = (max_left - nums[j]) * suffix_max[j + 1]
answer = max(answer, candidate)
max_left = max(max_left, nums[j])
return answer
The solution begins by constructing the suffix maximum array. Each entry stores the largest value that appears at or after that position. This allows constant-time access to the best possible right-side element for every middle index.
Next, max_left tracks the largest value seen so far while scanning from left to right. When processing a middle index j, this variable already contains the largest valid value for nums[i].
For each middle position, the algorithm computes the best possible triplet value using the largest available element on both sides. The answer is updated whenever a larger value is found.
Finally, the algorithm returns the maximum value discovered. Since answer is initialized to 0, negative candidates are automatically ignored, satisfying the problem requirement.
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]
}
}
maxLeft := nums[0]
var answer int64 = 0
for j := 1; j < n-1; j++ {
candidate := int64(maxLeft-nums[j]) * int64(suffixMax[j+1])
if candidate > answer {
answer = candidate
}
if nums[j] > maxLeft {
maxLeft = nums[j]
}
}
return answer
}
The Go implementation follows exactly the same logic as the Python version.
The main difference is integer handling. Since the result may reach approximately 10^12, the multiplication is performed using int64. Without this conversion, integer overflow could occur on systems where int is only 32 bits.
No special handling for empty arrays is required because the constraints guarantee at least three elements.
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 | max_left | nums[j] | best_right | 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 | max_left | nums[j] | best_right | 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 | max_left | nums[j] | best_right | Candidate | Answer |
|---|---|---|---|---|---|
| 1 | 1 | 2 | 3 | -3 | 0 |
Final answer:
0
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | One pass to build suffix maximums and one pass to evaluate middle indices |
| Space | O(n) | Suffix maximum array stores one value per element |
The algorithm performs only two linear scans of the array. Every operation inside the loops is constant time, resulting in an overall time complexity of O(n). The extra memory comes entirely 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, 1, 5]) == 20 # exactly one positive triplet
assert s.maximumTripletValue([10, 1, 1]) == 9 # minimum length, positive result
assert s.maximumTripletValue([1, 10, 1]) == 0 # minimum length, negative result
assert s.maximumTripletValue([100, 50, 1, 100]) == 9900 # large difference and multiplier
assert s.maximumTripletValue([7, 7, 7, 7]) == 0 # all equal values
assert s.maximumTripletValue([9, 8, 7, 6, 5]) == 10 # decreasing sequence
assert s.maximumTripletValue([1, 2, 100, 3, 100]) == 9700 # best left occurs in middle
assert s.maximumTripletValue([1000000, 1, 1000000]) == 999999000000 # large values
Test Summary
| Test | Why |
|---|---|
[12,6,1,2,7] |
Official example 1 |
[1,10,3,4,19] |
Official example 2 |
[1,2,3] |
Official example 3, negative result |
[5,1,5] |
Smallest positive case |
[10,1,1] |
Minimum array size with positive answer |
[1,10,1] |
Minimum array size with negative answer |
[100,50,1,100] |
Large difference and large multiplier |
[7,7,7,7] |
Equal values everywhere |
[9,8,7,6,5] |
Monotonically decreasing array |
[1,2,100,3,100] |
Best left value appears later |
[1000000,1,1000000] |
Verifies 64-bit arithmetic |
Edge Cases
One important edge case occurs when every possible triplet produces a negative value. For example, nums = [1, 2, 3]. The only triplet yields -3, but the problem requires returning 0. Initializing the answer to 0 automatically handles this scenario because negative candidates never replace the current answer.
Another important case is the minimum valid array size of three elements. In this situation there is exactly one possible triplet. Algorithms that incorrectly assume multiple choices for i, j, or k can fail here. The implementation correctly processes the single middle index and evaluates the only valid triplet.
A third edge case involves very large values. Since each element can be as large as 10^6, the final result can approach 10^{12}. A 32-bit integer cannot store such values safely. The Go implementation explicitly converts values to int64 before multiplication, ensuring that overflow does not occur.
A fourth edge case occurs when the optimal triplet does not use adjacent elements. For example, [100, 50, 1, 100] achieves its best value by selecting elements spread across the array. Because the algorithm stores the maximum value on each side of every middle index, it naturally considers such non-local optimal choices without requiring explicit triplet enumeration.