Maximum Value of an Ordered Triplet I solution and explanation
Google
9 more videos on this problem
Maximum Value of an Ordered Triplet I | Multiple Approaches | Leetcode 2873 | codestorywithMIKcodestorywithMIK · 19:19 · 10K views
Maximum Value of an Ordered Triplet I - Leetcode 2873 - PythonNeetCodeIO · 11:47 · 9K views
2873. Maximum Value of an Ordered Triplet I (Leetcode Easy)Programming Live with Larry · 3:02 · 716 views
Leetcode 2873 || Maximum Value of an Ordered Triplet I ||Leetcode Weekly Easy || cppKomal Pal · 5:59 · 482 views
✅ LeetCode 2873 Maximum Value of an Ordered Triplet I | Array | Preprocessing 🔥Code Harmony · 23:30 · 177 views
Maximum Value of an Ordered Triplet I | II || Leetcode 2873 || Leetcode 2874Knowledge Center · 10:56 · 138 views
LeetCode Problem 2873: Maximum Value of an Ordered Triplet I!Yingquan Li · 9:17 · 66 views
leetcode 2873 || Maximum Value of an Ordered Triplet I || In PythonEr. Navneet Kushwaha · 3:02 · 64 views
Maximum Value of an Ordered Triplet I - Leetcode 2873 - PythonTim Huang · 6:17 · 60 views
2873. Maximum Value of an Ordered Triplet I | Leetcode Daily - PythonLeetcode Daily · 8:13 · 54 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 <= 1001 <= nums[i] <= 106
Approach overview
Problem Overview: You are given an integer array nums. The goal is to compute the maximum value of the expression (nums[i] - nums[j]) * nums[k] such that i < j < k. If every possible value is negative, return 0. The challenge is efficiently evaluating valid triplets while respecting the index ordering constraint.
Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)
The most direct method checks every ordered triplet (i, j, k) where i < j < k. Use three nested loops: the outer loop selects i, the second selects j, and the third selects k. For each combination, compute (nums[i] - nums[j]) * nums[k] and track the maximum value seen. This approach is useful for verifying correctness and understanding the problem constraints, but it quickly becomes impractical because the number of triplets grows cubically. With arrays of size n, the runtime is O(n^3) and the algorithm uses constant extra memory O(1). This method works only for very small inputs.
Approach 2: Prefix and Suffix Maximums (O(n) time, O(n) space)
The expression (nums[i] - nums[j]) * nums[k] can be maximized by selecting the largest possible nums[i] before j and the largest possible nums[k] after j. Instead of enumerating every triplet, precompute helpful values. First build a prefix array where prefixMax[j] stores the maximum element from index 0 to j. Then build a suffix array where suffixMax[j] stores the maximum element from index j to the end of the array.
Now treat each index j as the middle element of the triplet. The best candidate on the left is prefixMax[j-1], and the best candidate on the right is suffixMax[j+1]. Compute the value (prefixMax[j-1] - nums[j]) * suffixMax[j+1] and update the global maximum. This reduces the search from three nested loops to a single pass over the array after preprocessing. The overall complexity becomes O(n) time with O(n) extra memory.
This technique works because the best triplet for a fixed j must use the maximum available value on both sides to maximize the difference and the multiplier. Precomputing those values avoids repeated scanning of the array.
The solution relies on simple preprocessing over an array and a classic prefix/suffix preprocessing pattern often used in problems involving range maximum queries. Variants of this idea appear frequently in optimization problems where each index acts as a pivot.
Recommended for interviews: The prefix and suffix maximum approach. Interviewers expect candidates to move beyond brute force and recognize that the optimal i and k for each j are simply the maximum values on each side. Implementing this in O(n) time shows strong problem‑decomposition skills while keeping the code straightforward.
Approach 1: Brute Force Approach
This approach involves iterating through all possible triplet indices.
We loop through all positions for i, j, and k while maintaining the required i < j < k condition, and for each triplet, we compute the value and maintain the maximum encountered.
While this approach is simple, it's not efficient for large arrays due to its O(n^3) time complexity.
def maxTripletValue(nums):
n = len(nums)
max_value = 0
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
value = (nums[i] - nums[j]) * nums[k]
max_value = max(max_value, value)
return max_valuefunction maxTripletValue(nums) {
let n = nums.length;
let maxValue = 0;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
for (let k = j + 1; k < n; k++) {
let value = (nums[i] - nums[j]) * nums[k];
maxValue = Math.max(maxValue, value);
}
}
}
return maxValue;
}This Python function loops through each combination of i, j, and k, calculates the triplet value, and tracks the maximum value seen.
Time complexity: O(n^3)
Space complexity: O(1)
Approach 2: Optimized Approach with Prefix and Suffix Arrays
This approach aims to reduce repetitive calculations by maintaining prefix and suffix arrays.
The idea is to preprocess information to find the maximum elements before and after any element, thereby facilitating quick look-up while iterating through the central elements of the triplets.
def maxTripletValue(nums):
n = len(nums)
if n < 3:
return 0
max_suff = [0] * n
max_suff[n-1] = nums[n-1]
for i in range(n-2, -1, -1):
max_suff[i] = max(nums[i], max_suff[i + 1])
max_value = 0
max_pref = nums[0]
for j in range(1, n-1):
max_value = max(max_value, (max_pref - nums[j]) * max_suff[j + 1])
max_pref = max(max_pref, nums[j])
return max_value#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
int maxTripletValue(vector<int>& nums) {
int n = nums.size();
if (n < 3) return 0;
vector<int> max_suff(n);
max_suff[n-1] = nums[n-1];
for (int i = n-2; i >= 0; --i) {
max_suff[i] = max(nums[i], max_suff[i + 1]);
}
int max_value = 0;
int max_pref = nums[0];
for (int j = 1; j < n-1; ++j) {
max_value = max(max_value, (max_pref - nums[j]) * max_suff[j + 1]);
max_pref = max(max_pref, nums[j]);
}
return max_value;
}This Python solution uses prefix and suffix arrays to maintain the maximum values up to each point. This allows an O(n^2) solution, significantly reducing the time compared to the brute force method.
Time complexity: O(n^2)
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).
class Solution {
public long maximumTripletValue(int[] nums) {
long ans = 0, mxDiff = 0;
int mx = 0;
for (int x : nums) {
ans = Math.max(ans, mxDiff * x);
mxDiff = Math.max(mxDiff, mx - x);
mx = Math.max(mx, x);
}
return ans;
}
}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 with Prefix and Suffix Arrays | Time complexity: O(n^2) |
| 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 validating small test cases |
| Prefix and Suffix Maximum Arrays | O(n) | O(n) | Best general solution for large arrays and interview settings |
Frequently asked questions
Is Maximum Value of an Ordered Triplet I easy or hard?
The problem is categorized as Easy on LeetCode. The brute force idea is straightforward, but recognizing the prefix and suffix optimization is the key step that reduces the complexity to O(n).
How to solve Maximum Value of an Ordered Triplet I in O(n)?
Precompute prefix maximum values so you know the largest nums[i] to the left of each index. Also compute suffix maximum values to know the largest nums[k] to the right. Treat each index j as the middle element and compute (prefixMax[j-1] - nums[j]) * suffixMax[j+1], updating the maximum result during a single pass.
Maximum Value of an Ordered Triplet I Python or C++ solution
Python and C++ implementations typically build prefixMax and suffixMax arrays first. Then they iterate through the array treating each index as j, compute the candidate value using the precomputed maximums, and track the maximum result. This implementation runs in O(n) time.
What is the best approach for Maximum Value of an Ordered Triplet I?
The optimal approach uses prefix and suffix maximum arrays. For each index j, track the largest value before it (best i) and the largest value after it (best k). This allows computing (nums[i] - nums[j]) * nums[k] in a single pass. The overall complexity becomes O(n) time with O(n) extra space.
What data structure is used in Maximum Value of an Ordered Triplet I?
The solution primarily uses arrays. Two auxiliary arrays store prefix maximum values and suffix maximum values so the algorithm can quickly access the best candidate elements on both sides of the middle index.
What is the time complexity of Maximum Value of an Ordered Triplet I?
The brute force solution runs in O(n^3) time because it checks every possible ordered triplet. The optimized solution with prefix and suffix maximum arrays runs in O(n) time since it preprocesses the array and evaluates each index once.
Is Maximum Value of an Ordered Triplet I asked at Google, Amazon, or Meta?
Problems involving ordered triplets, prefix preprocessing, and array optimization frequently appear in technical interviews at large companies such as Amazon, Google, and Meta. While the exact problem may vary, the technique of using prefix and suffix maximums is a common interview pattern.