Maximum Value of an Ordered Triplet II
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to use brute force. We can generate every possible ordered triplet of indices (i, j, k) where i < j < k, calculate the value (nums[i] - nums[j]) * nums[k] for each triplet, and keep track of the maximum value found. We initialize our maximum value to 0, as the problem states to return 0 if all triplet values are negative.
Algorithm
- Initialize a variable
maxValueto 0, using alongdata type to prevent potential overflow. - Use three nested loops to iterate through all possible combinations of indices
(i, j, k)such thati < j < k.- The outer loop for
iruns from0ton-3. - The middle loop for
jruns fromi+1ton-2. - The inner loop for
kruns fromj+1ton-1.
- The outer loop for
- Inside the innermost loop, calculate the value of the triplet:
currentValue = (long)(nums[i] - nums[j]) * nums[k]. - Compare
currentValuewithmaxValueand updatemaxValueifcurrentValueis greater:maxValue = Math.max(maxValue, currentValue). - After the loops complete,
maxValuewill hold the maximum possible value. Since the problem asks to return 0 for negative results, and ourmaxValueis initialized to 0 and only updated with larger values, this condition is naturally met. - Return
maxValue.
Walkthrough
This method involves three nested loops. The first loop iterates through the index i from the beginning of the array. The second loop iterates through j starting from i + 1, and the third loop iterates through k starting from j + 1. This ensures that we only consider valid ordered triplets (i < j < k). For each triplet, we compute its value and update our overall maximum. Using a long for the result is crucial to avoid integer overflow, as the product can exceed the capacity of a standard 32-bit integer.
class Solution { public long maximumValueSum(int[] nums) { int n = nums.length; long maxValue = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { long currentValue = (long)(nums[i] - nums[j]) * nums[k]; if (currentValue > maxValue) { maxValue = currentValue; } } } } return maxValue; }}Complexity
Time
O(N^3) - Where N is the length of the `nums` array. The three nested loops lead to a cubic time complexity, which is too slow for N up to 10^5.
Space
O(1) - Constant extra space is used, as we only need a few variables to store the loop indices and the maximum value.
Trade-offs
Pros
Simple to understand and implement.
Correct for small input sizes.
Cons
Extremely inefficient for large inputs.
Will result in a 'Time Limit Exceeded' (TLE) error on most platforms for the given constraints.
We can significantly improve the time complexity by avoiding the innermost loop. If we fix the middle index j, our goal is to find the maximum nums[i] for all i < j and the maximum nums[k] for all k > j. Instead of recalculating these maximums for each j, we can precompute them in linear time.
Algorithm
- The goal is to maximize
(nums[i] - nums[j]) * nums[k]. - For a fixed middle index
j, the value is maximized whennums[i](fori < j) is as large as possible andnums[k](fork > j) is as large as possible (sincenums[k]is positive). - We can precompute the maximum values for all prefixes and suffixes of the array.
- Create a
prefixMaxarray of sizen, whereprefixMax[i]stores the maximum value innums[0...i]. - Create a
suffixMaxarray of sizen, wheresuffixMax[i]stores the maximum value innums[i...n-1]. - Initialize
maxValue = 0L. - Iterate with a single loop for
jfrom1ton-2. - For each
j, the maximumnums[i]fori < jisprefixMax[j-1], and the maximumnums[k]fork > jissuffixMax[j+1]. - Calculate the potential maximum for this
j:currentValue = (long)(prefixMax[j-1] - nums[j]) * suffixMax[j+1]. - Update the overall maximum:
maxValue = Math.max(maxValue, currentValue). - Return
maxValue.
Walkthrough
This approach involves two main steps. First, we perform two passes over the array to create helper arrays. The prefixMax array is built from left to right, where prefixMax[i] = max(prefixMax[i-1], nums[i]). The suffixMax array is built from right to left, where suffixMax[i] = max(suffixMax[i+1], nums[i]).
After precomputation, we iterate through the array a final time, considering each element nums[j] (for 1 <= j <= n-2) as the middle element of the triplet. For each j, we can find the required maximums max(nums[i]) and max(nums[k]) in O(1) time using our precomputed arrays. This reduces the overall time complexity to be linear.
class Solution { public long maximumValueSum(int[] nums) { int n = nums.length; if (n < 3) { return 0; } int[] prefixMax = new int[n]; prefixMax[0] = nums[0]; for (int i = 1; i < n; i++) { prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]); } int[] suffixMax = new int[n]; suffixMax[n - 1] = nums[n - 1]; for (int i = n - 2; i >= 0; i--) { suffixMax[i] = Math.max(suffixMax[i + 1], nums[i]); } long maxValue = 0; for (int j = 1; j < n - 1; j++) { long val_i = prefixMax[j - 1]; long val_k = suffixMax[j + 1]; long currentValue = (val_i - nums[j]) * val_k; if (currentValue > maxValue) { maxValue = currentValue; } } return maxValue; }}Complexity
Time
O(N) - We make three separate passes through the array (one for prefix max, one for suffix max, and one for the final calculation), each taking linear time. Thus, the total time complexity is O(N) + O(N) + O(N) = O(N).
Space
O(N) - We use two additional arrays, `prefixMax` and `suffixMax`, each of size N.
Trade-offs
Pros
Significantly more time-efficient than the brute-force approach.
Guaranteed to pass within the time limits for the given constraints.
Cons
Requires extra space proportional to the input size, which might be a concern for very large arrays in memory-constrained environments.
The most optimal solution improves upon the previous approach by eliminating the need for extra space. We can achieve O(1) space complexity by calculating the necessary maximums on the fly within a single pass. The key idea is to iterate through the array and, for each potential third element nums[k], find the best possible (nums[i] - nums[j]) part from the elements that appeared before it.
Algorithm
- The expression to maximize is
(nums[i] - nums[j]) * nums[k]. - We can iterate through the array and at each position
p, considernums[p]asnums[k]. To get the max value, we need to multiplynums[p]by the maximum possible value of(nums[i] - nums[j])wherei < j < p. - We can find this maximum
(nums[i] - nums[j])part iteratively in a single pass. - Initialize
ans = 0L,max_i_val = nums[0], andmax_prefix_diff = 0.max_i_valwill track the maximumnums[i]seen so far.max_prefix_diffwill track the maximum(nums[i] - nums[j])seen so far.
- Iterate
jfrom1ton-2. - In each iteration,
max_i_valholds the maximum value innums[0...j-1]. We can form a new potential differencemax_i_val - nums[j]. Updatemax_prefix_diff = Math.max(max_prefix_diff, max_i_val - nums[j]). - Now,
max_prefix_diffholds the maximum possible value for(nums[a] - nums[b])wherea < b <= j. The elementnums[j+1]can serve as ournums[k]. - Calculate a potential answer:
ans = Math.max(ans, (long)max_prefix_diff * nums[j+1]). - Before the next iteration, update
max_i_valto include the current element:max_i_val = Math.max(max_i_val, nums[j]). - Return
ans.
Walkthrough
We iterate through the array from left to right, maintaining two key variables. The first, max_i_val, keeps track of the maximum element value encountered so far, which represents the best possible nums[i]. The second, max_prefix_diff, tracks the maximum difference (nums[i] - nums[j]) found so far.
As we iterate with index j from 1 to n-2, we treat nums[j] as a potential middle element. We update max_prefix_diff using the current max_i_val and nums[j]. Then, we consider nums[j+1] as a potential third element nums[k] and calculate a candidate for the maximum triplet value by multiplying it with the current max_prefix_diff. Finally, we update max_i_val to include nums[j] before proceeding to the next iteration. This dynamic programming approach ensures we find the maximum value in a single pass with constant extra space.
class Solution { public long maximumValueSum(int[] nums) { int n = nums.length; long ans = 0; // max_i_val will store the maximum of nums[i] for i < j int max_i_val = nums[0]; // max_prefix_diff will store the maximum of (nums[i] - nums[j]) for i < j int max_prefix_diff = 0; // We iterate j from 1 to n-2. In each iteration, we consider nums[j+1] as nums[k]. for (int j = 1; j < n - 1; j++) { // Update the maximum possible difference (nums[i] - nums[j]) found so far. // For the current nums[j], the best nums[i] is the max value before it (max_i_val). max_prefix_diff = Math.max(max_prefix_diff, max_i_val - nums[j]); // The current max_prefix_diff is the best (nums[a] - nums[b]) for a < b <= j. // We can pair this with nums[j+1] as our nums[k]. ans = Math.max(ans, (long)max_prefix_diff * nums[j + 1]); // Update max_i_val to include nums[j] for the next iteration. max_i_val = Math.max(max_i_val, nums[j]); } return ans; }}Complexity
Time
O(N) - We iterate through the array only once, performing constant time operations at each step.
Space
O(1) - This approach uses only a few variables to store the running maximums, regardless of the input size.
Trade-offs
Pros
Optimal time complexity of O(N).
Optimal space complexity of O(1).
Most efficient solution for the given problem.
Cons
The logic can be less intuitive to grasp compared to the precomputation method.
Solutions
Solution
class Solution {public long maximumTripletValue(int[] nums) { long max, maxDiff, ans; max = 0; maxDiff = 0; ans = 0; for (int num : nums) { ans = Math.max(ans, num * maxDiff); max = Math.max(max, num); maxDiff = Math.max(maxDiff, max - num); } return ans; }}class Solution {public: long long maximumTripletValue(vector<int> &nums) { long long ans = 0; int mx = 0, mx_diff = 0; for (int num : nums) { ans = max(ans, 1LL * mx_diff * num); mx = max(mx, num); mx_diff = max(mx_diff, mx - num); } return ans; }};class Solution: def maximumTripletValue(self, nums: List[int]) -> int: ans = mx = mx_diff = 0 for num in nums: ans = max(ans, mx_diff * num) mx = max(mx, num) mx_diff = max(mx_diff, mx - num) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.