Skip to main content
Talentd

Maximum Value of an Ordered Triplet II - Solution & Explanation

MediumArray16 min readAsked at: Amazon, Microsoft, Google +2
Practice this problem

Problem Statement

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 <= 105
  • 1 <= 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.

The C solution initializes a variable to hold the maximum triplet value at 0, selects all triplets (i, j, k) through nested loops, calculates their values, and updates the maximum if a higher value is found.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^3), as there are three nested loops; each with a progression over the length of the array.
Space Complexity: O(1), as no extra space is used proportional to input size.

Try this approach in the editor →

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.

With C, we track and store the minimum middle and maximum left values as we iterate through the array. By efficiently managing these values, we reduce unnecessary loop iteration, evaluating only necessary calculations for triplet potential.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), as it iterates through the array to build the minJ and maxI arrays.
Space Complexity: O(n), due to the auxiliary arrays used.

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(n^3), as there are three nested loops; each with a progression over the length of the array.
Space Complexity: O(1), as no extra space is used proportional to input size.

Optimized Approach

Time Complexity: O(n), as it iterates through the array to build the minJ and maxI arrays.
Space Complexity: O(n), due to the auxiliary arrays used.

Maintaining Prefix Maximum and Maximum Difference—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Triplet EnumerationO(n^3)O(1)Useful for understanding the problem or when constraints are extremely small
Prefix Maximum + Best Difference TrackingO(n)O(1)Best general solution for large arrays and typical interview settings

Video Solution

Maximum Value of an Ordered Triplet II - Leetcode 2874 - Python • NeetCodeIO • 8,926 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Maximum Value of an Ordered Triplet II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Sum of Mountain Triplets II

Next

Sum of Beauty in the Array