Maximum Value of an Ordered Triplet II solution and explanation
Google
9 more videos on this problem
Maximum Value of an Ordered Triplet II - Leetcode 2874 - PythonNeetCodeIO · 14:28 · 8K views
Maximum Value of an Ordered Triplet I and II | Leetcode 2874 | Leetcode 2873Techdose · 22:36 · 6K views
2874. Maximum Value of an Ordered Triplet II (Leetcode Medium)Programming Live with Larry · 7:29 · 980 views
LeetCode 2874 Maximum Value of an Ordered Triplet II | Array | Preprocessing | Asked in Media.netCode Harmony · 8:30 · 507 views
Leetcode 2874 || Maximum Value of an Ordered Triplet II ||Leetcode Weekly Easy || cppKomal Pal · 14:45 · 313 views
Maximum Value of an Ordered Triplet I | II || Leetcode 2873 || Leetcode 2874Knowledge Center · 10:56 · 138 views
LeetCode 2874 | Maximum value of an ordered triplet II | Python | April 4 |OverClocked Dev · 11:55 · 128 views
Maximum Value of an Ordered Triplet II - Leetcode 2874ThinkOutsideTheBox · 1:36 · 117 views
Leetcode-2874. Maximum Value of an Ordered Triplet IICode With Nani · 6:27 · 57 views
Maximum Value of an Ordered Triplet II - Leetcode 2874 - PythonTim Huang · 4:05 · 51 views
The problem
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].
Example 1:
Input: nums = [12,6,1,2,7] Output: 77 Explanation: The value of the triplet (0, 2, 4) is (nums[0] - nums[2]) * nums[4] = 77. It can be shown that there are no ordered triplets of indices with a value greater than 77.
Example 2:
Input: nums = [1,10,3,4,19] Output: 133 Explanation: The value of the triplet (1, 2, 4) is (nums[1] - nums[2]) * nums[4] = 133. It can be shown that there are no ordered triplets of indices with a value greater than 133.
Example 3:
Input: nums = [1,2,3] Output: 0 Explanation: The only ordered triplet of indices (0, 1, 2) has a negative value of (nums[0] - nums[1]) * nums[2] = -3. Hence, the answer would be 0.
Constraints:
3 <= nums.length <= 1051 <= nums[i] <= 106
Approach overview
Problem Overview: You are given an integer array nums. Choose indices i < j < k that maximize the expression (nums[i] - nums[j]) * nums[k]. If every combination produces a negative value, the result should be 0. The challenge is respecting the index order while searching for the largest possible product.
Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)
The most direct method checks every valid triplet. Use three nested loops: the first picks i, the second picks j where j > i, and the third picks k where k > j. For each combination compute (nums[i] - nums[j]) * nums[k] and keep the maximum value encountered. This guarantees correctness because every ordered triplet is evaluated. The downside is performance: the algorithm performs roughly n^3 operations, which becomes impractical once the array grows beyond a few hundred elements.
Approach 2: Prefix Maximum + Best Difference Tracking (O(n) time, O(1) space)
The expression can be rearranged conceptually into two parts: first maximize (nums[i] - nums[j]) for i < j, then multiply it with nums[k] where k > j. While scanning the array, maintain the largest value seen so far for nums[i]. For each potential middle index j, compute the difference maxPrefix - nums[j]. Track the best difference encountered so far because any future k can use it. When visiting a new index as k, multiply nums[k] with the stored maximum difference and update the answer. This transforms the search from three nested loops into a single linear pass using constant extra memory.
This strategy relies on maintaining prefix information, a common pattern in array problems. By compressing earlier choices into running values (maxPrefix and maxDiff), the algorithm avoids recomputation and achieves linear time. The technique is closely related to prefix techniques and greedy-style updates often used in high‑performance greedy scans.
Recommended for interviews: The linear scan with prefix tracking is the expected solution. Interviewers want to see that you recognize how to separate the triplet expression into reusable intermediate values. Mentioning the brute force solution first demonstrates understanding of the constraints, but deriving the O(n) approach shows stronger algorithmic reasoning.
Approach 1: Brute Force Approach
In this approach, we examine every possible triplet (i, j, k) where i < j < k. By iterating through all combinations, we calculate the value (nums[i] - nums[j]) * nums[k] for each, keeping track of the maximum value encountered.
Although simple to implement, it's inefficient for large arrays because of the O(n^3) time complexity.
def max_triplet_value(nums):
max_value = 0
n = len(nums)
for i in range(n - 2):
for j in range(i + 1, n - 1):
for k in range(j + 1, n):
current_value = (nums[i] - nums[j]) * nums[k]
max_value = max(max_value, current_value)
return max_value
# Example usage
nums = [12, 6, 1, 2, 7]
print("Max Triplet Value:", max_triplet_value(nums))public class Solution {
public int maxTripletValue(int[] nums) {
int maxValue = 0;
int n = nums.length;
for (int i = 0; i < n - 2; ++i) {
for (int j = i + 1; j < n - 1; ++j) {
for (int k = j + 1; k < n; ++k) {
int currentValue = (nums[i] - nums[j]) * nums[k];
maxValue = Math.max(maxValue, currentValue);
}
}
}
return maxValue;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {12, 6, 1, 2, 7};
System.out.println("Max Triplet Value: " + sol.maxTripletValue(nums));
}
}#include <vector>
#include <iostream>
int maxTripletValue(std::vector<int>& nums) {
int maxValue = 0;
int n = nums.size();
for (int i = 0; i < n - 2; ++i) {
for (int j = i + 1; j < n - 1; ++j) {
for (int k = j + 1; k < n; ++k) {
int currentValue = (nums[i] - nums[j]) * nums[k];
maxValue = std::max(maxValue, currentValue);
}
}
}
return maxValue;
}
int main() {
std::vector<int> nums = {12, 6, 1, 2, 7};
int result = maxTripletValue(nums);
std::cout << "Max Triplet Value: " << result << std::endl;
return 0;
}function maxTripletValue(nums) {
let maxValue = 0;
const n = nums.length;
for (let i = 0; i < n - 2; i++) {
for (let j = i + 1; j < n - 1; j++) {
for (let k = j + 1; k < n; k++) {
const currentValue = (nums[i] - nums[j]) * nums[k];
maxValue = Math.max(maxValue, currentValue);
}
}
}
return maxValue;
}
// Example usage
const nums = [12, 6, 1, 2, 7];
console.log("Max Triplet Value:", maxTripletValue(nums));#include <stdio.h>
#include <limits.h>
int maxTripletValue(int* nums, int numsSize) {
int maxValue = 0;
for (int i = 0; i < numsSize - 2; i++) {
for (int j = i + 1; j < numsSize - 1; j++) {
for (int k = j + 1; k < numsSize; k++) {
int currentValue = (nums[i] - nums[j]) * nums[k];
if (currentValue > maxValue) {
maxValue = currentValue;
}
}
}
}
return maxValue;
}
int main() {
int nums[] = {12, 6, 1, 2, 7};
int result = maxTripletValue(nums, 5);
printf("Max Triplet Value: %d\n", result);
return 0;
}using System;
class Solution {
public int MaxTripletValue(int[] nums) {
int maxValue = 0;
int n = nums.Length;
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
int currentValue = (nums[i] - nums[j]) * nums[k];
maxValue = Math.Max(maxValue, currentValue);
}
}
}
return maxValue;
}
static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {12, 6, 1, 2, 7};
Console.WriteLine("Max Triplet Value: " + sol.MaxTripletValue(nums));
}
}The Python solution checks all possible triplets, using the max function to ensure the highest value is retained.
Time Complexity: O(n^3).
Space Complexity: O(1).
Approach 2: Optimized Approach
This approach leverages extra data structures to track the smallest 'j' (middle) index values and the maximum 'i' (left) index values. We optimize our evaluation by computing the possible maximum difference before computing for each 'k' value.
This method greatly reduces the number of operations necessary compared to the brute force method.
def max_triplet_value(nums):
n = len(nums)
maxValue = 0
min_j = [0] * n
max_i = [0] * n
min_val = nums[1]
for j in range(1, n - 1):
min_val = min(min_val, nums[j])
min_j[j] = min_val
max_val = nums[0]
for i in range(n - 2):
max_val = max(max_val, nums[i])
max_i[i] = max_val
for k in range(n - 1, 1, -1):
potential = (max_i[k-2] - min_j[k-1]) * nums[k]
maxValue = max(maxValue, potential)
return maxValue
# Example usage
nums = [12, 6, 1, 2, 7]
print("Max Triplet Value:", max_triplet_value(nums))import java.util.*;
public class Solution {
public int maxTripletValue(int[] nums) {
int n = nums.length;
int maxValue = 0;
int[] minJ = new int[n], maxI = new int[n];
int minVal = nums[1];
for (int j = 1; j < n - 1; j++) {
minVal = Math.min(minVal, nums[j]);
minJ[j] = minVal;
}
int maxVal = nums[0];
for (int i = 0; i < n - 2; i++) {
maxVal = Math.max(maxVal, nums[i]);
maxI[i] = maxVal;
}
for (int k = n - 1; k >= 2; k--) {
int potential = (maxI[k-2] - minJ[k-1]) * nums[k];
maxValue = Math.max(maxValue, potential);
}
return maxValue;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {12, 6, 1, 2, 7};
System.out.println("Max Triplet Value: " + sol.maxTripletValue(nums));
}
}#include <vector>
#include <iostream>
#include <algorithm>
int maxTripletValue(const std::vector<int>& nums) {
int maxValue = 0;
int numsSize = nums.size();
std::vector<int> minJ(numsSize), maxI(numsSize);
int minVal = nums[1];
for (int j = 1; j < numsSize - 1; ++j) {
minVal = std::min(minVal, nums[j]);
minJ[j] = minVal;
}
int maxVal = nums[0];
for (int i = 0; i < numsSize - 2; ++i) {
maxVal = std::max(maxVal, nums[i]);
maxI[i] = maxVal;
}
for (int k = numsSize - 1; k >= 2; --k) {
int potential = (maxI[k-2] - minJ[k-1]) * nums[k];
maxValue = std::max(maxValue, potential);
}
return maxValue;
}
int main() {
std::vector<int> nums = {12, 6, 1, 2, 7};
std::cout << "Max Triplet Value: " << maxTripletValue(nums) << std::endl;
return 0;
}function maxTripletValue(nums) {
const n = nums.length;
let maxValue = 0;
const minJ = Array(n).fill(0);
const maxI = Array(n).fill(0);
let minVal = nums[1];
for (let j = 1; j < n - 1; j++) {
minVal = Math.min(minVal, nums[j]);
minJ[j] = minVal;
}
let maxVal = nums[0];
for (let i = 0; i < n - 2; i++) {
maxVal = Math.max(maxVal, nums[i]);
maxI[i] = maxVal;
}
for (let k = n - 1; k >= 2; k--) {
const potential = (maxI[k-2] - minJ[k-1]) * nums[k];
maxValue = Math.max(maxValue, potential);
}
return maxValue;
}
// Example usage
const nums = [12, 6, 1, 2, 7];
console.log("Max Triplet Value:", maxTripletValue(nums));#include <stdio.h>
#include <limits.h>
int maxTripletValue(int* nums, int numsSize) {
int maxValue = 0;
int minJ[numsSize], maxI[numsSize];
int minVal = nums[1];
for (int j = 1; j < numsSize - 1; j++) {
if (nums[j] < minVal) {
minVal = nums[j];
}
minJ[j] = minVal;
}
int maxVal = nums[0];
for (int i = 0; i < numsSize - 2; i++) {
if (nums[i] > maxVal) {
maxVal = nums[i];
}
maxI[i] = maxVal;
}
for (int k = numsSize - 1; k >= 2; k--) {
int potential = (maxI[k-2] - minJ[k-1]) * nums[k];
if (potential > maxValue) {
maxValue = potential;
}
}
return maxValue;
}
int main() {
int nums[] = {12, 6, 1, 2, 7};
int result = maxTripletValue(nums, 5);
printf("Max Triplet Value: %d\n", result);
return 0;
}using System;
class Solution {
public int MaxTripletValue(int[] nums) {
int n = nums.Length;
int maxValue = 0;
int[] minJ = new int[n];
int[] maxI = new int[n];
int minVal = nums[1];
for (int j = 1; j < n - 1; j++) {
minVal = Math.Min(minVal, nums[j]);
minJ[j] = minVal;
}
int maxVal = nums[0];
for (int i = 0; i < n - 2; i++) {
maxVal = Math.Max(maxVal, nums[i]);
maxI[i] = maxVal;
}
for (int k = n - 1; k >= 2; k--) {
int potential = (maxI[k-2] - minJ[k-1]) * nums[k];
maxValue = Math.Max(maxValue, potential);
}
return maxValue;
}
static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {12, 6, 1, 2, 7};
Console.WriteLine("Max Triplet Value: " + sol.MaxTripletValue(nums));
}
}The optimized Python solution makes use of prefilled lists for quick lookups when determining triplet value, rather than recalculating minis and maxes, thus maintaining O(n) operations.
Time Complexity: O(n).
Space Complexity: O(n).
Approach 3: Maintaining Prefix Maximum and Maximum Difference
We use two variables mx and mxDiff to maintain the prefix maximum value and maximum difference, respectively, and use a variable ans to maintain the answer. Initially, these variables are all 0.
Next, we iterate through each element x in the array as nums[k]. First, we update the answer ans = max(ans, mxDiff times x). Then we update the maximum difference mxDiff = max(mxDiff, mx - x). Finally, we update the prefix maximum value mx = max(mx, x).
After iterating through all elements, we return the answer ans.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
function maximumTripletValue(nums: number[]): number {
let [ans, mx, mxDiff] = [0, 0, 0];
for (const x of nums) {
ans = Math.max(ans, mxDiff * x);
mxDiff = Math.max(mxDiff, mx - x);
mx = Math.max(mx, x);
}
return ans;
}func maximumTripletValue(nums []int) int64 {
ans, mx, mxDiff := 0, 0, 0
for _, x := range nums {
ans = max(ans, mxDiff*x)
mxDiff = max(mxDiff, mx-x)
mx = max(mx, x)
}
return int64(ans)
}impl Solution {
pub fn maximum_triplet_value(nums: Vec<i32>) -> i64 {
let mut ans: i64 = 0;
let mut mx: i32 = 0;
let mut mx_diff: i32 = 0;
for &x in &nums {
ans = ans.max(mx_diff as i64 * x as i64);
mx_diff = mx_diff.max(mx - x);
mx = mx.max(x);
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3). |
| Optimized Approach | Time Complexity: O(n). |
| Maintaining Prefix Maximum and Maximum Difference | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Triplet Enumeration | O(n^3) | O(1) | Useful for understanding the problem or when constraints are extremely small |
| Prefix Maximum + Best Difference Tracking | O(n) | O(1) | Best general solution for large arrays and typical interview settings |
Frequently asked questions
Is Maximum Value of an Ordered Triplet II easy or hard?
Maximum Value of an Ordered Triplet II is rated Medium. The brute force idea is straightforward, but recognizing that the expression can be broken into prefix maximum and running difference requires algorithmic insight.
Maximum Value of an Ordered Triplet II Python/Java solution
Most implementations follow the same pattern: track maxPrefix, compute diff = maxPrefix - nums[j], maintain maxDiff, and evaluate maxDiff * nums[k]. This logic translates directly across Python, Java, C++, and other languages with identical O(n) time complexity.
How to solve Maximum Value of an Ordered Triplet II in O(n)?
Scan the array while maintaining two values: the largest prefix value nums[i] and the maximum difference (nums[i] - nums[j]). Each time you reach a new element as k, compute maxDiff * nums[k] to update the answer. Update prefix values and differences as you iterate, ensuring the order i < j < k is preserved.
What is the best approach for Maximum Value of an Ordered Triplet II?
The optimal solution uses a single pass with prefix tracking. Maintain the maximum value seen so far for nums[i], compute the best difference (nums[i] - nums[j]) while scanning, and multiply it with nums[k] for later elements. This reduces the problem to O(n) time and O(1) space.
Is Maximum Value of an Ordered Triplet II asked at Google/Amazon/Meta?
Array optimization problems with prefix tracking frequently appear in interviews at companies like Amazon, Google, and Meta. While the exact problem number may vary, the underlying pattern—compressing earlier choices into prefix values for a linear scan—is commonly tested.
What data structure is used in Maximum Value of an Ordered Triplet II?
The solution mainly relies on simple variables and prefix tracking over an array. No advanced data structures are required; maintaining running maximum values and differences is sufficient to compute the optimal result efficiently.
What is the time complexity of Maximum Value of an Ordered Triplet II?
The brute force method requires O(n^3) time because it evaluates every possible ordered triplet (i, j, k). The optimized solution runs in O(n) time by tracking a prefix maximum and the best difference seen so far, while using constant extra memory.