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] <= 106Problem 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.
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.
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.
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.
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.
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).
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3), as there are three nested loops; each with a progression over the length of the array. |
| Optimized Approach | Time Complexity: O(n), as it iterates through the array to build the minJ and maxI arrays. |
| Maintaining Prefix Maximum and Maximum Difference | — |
| 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 |
Maximum Value of an Ordered Triplet II - Leetcode 2874 - Python • NeetCodeIO • 8,858 views views
Watch 9 more video solutions →Practice Maximum Value of an Ordered Triplet II with our built-in code editor and test cases.
Practice on FleetCode