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] <= 106Problem 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.
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.
This Python function loops through each combination of i, j, and k, calculates the triplet value, and tracks the maximum value seen.
Python
JavaScript
Time complexity: O(n^3)
Space complexity: O(1)
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.
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)
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) |
| Optimized Approach with Prefix and Suffix Arrays | Time complexity: O(n^2) |
| 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 validating small test cases |
| Prefix and Suffix Maximum Arrays | O(n) | O(n) | Best general solution for large arrays and interview settings |
Maximum Value of an Ordered Triplet I | Multiple Approaches | Leetcode 2873 | codestorywithMIK • codestorywithMIK • 10,138 views views
Watch 9 more video solutions →Practice Maximum Value of an Ordered Triplet I with our built-in code editor and test cases.
Practice on FleetCode