Maximum Value of an Ordered Triplet I
EasyPrompt
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
Approaches
4 approaches with complexity analysis and trade-offs.
The most optimal solution achieves both linear time and constant space complexity by processing the array in a single pass. This dynamic programming-style approach cleverly maintains the maximums needed at each step. As we iterate through the array, we consider each element as a potential nums[k], nums[j], and nums[i] in a specific order to build up the solution.
Algorithm
- Initialize
maxVal = 0,max_i = 0, andmax_ij = 0. max_iwill track the maximumnums[i]seen so far.max_ijwill track the maximumnums[i] - nums[j]seen so far.- Iterate through each
numin thenumsarray. - In each iteration, first update the result:
maxVal = max(maxVal, (long)max_ij * num). Here,numacts asnums[k]. - Then, update the maximum difference:
max_ij = max(max_ij, max_i - num). Here,numacts asnums[j]. - Finally, update the maximum prefix value:
max_i = max(max_i, num). Here,numacts asnums[i]. - Return
maxVal.
Walkthrough
We iterate through the array while maintaining two key values:
max_i: The maximum value of an element seen so far (a potentialnums[i]).max_ij: The maximum differencenums[i] - nums[j]seen so far.
For each number num in the array, we perform three updates in a specific order:
- Treat
numasnums[k]: We calculate a potential answer by multiplyingnumwith the best(nums[i] - nums[j])difference (max_ij) found among the elements beforenum. We update our overallmaxValwith this result. - Treat
numasnums[j]: We updatemax_ij. A new, larger difference might be formed by usingnumasnums[j]and the largest element seen before it (max_i) asnums[i]. So we updatemax_ij = max(max_ij, max_i - num). - Treat
numasnums[i]: We updatemax_iby comparing it with the currentnum. This ensuresmax_iis ready for future elements to use as their potentialnums[j]ornums[k].
The strict order of these updates is crucial for the correctness of the algorithm.
class Solution { public long maximumValue(int[] nums) { long maxVal = 0; int max_i = 0; int max_ij = 0; for (int num : nums) { // Current num is nums[k]. max_ij is max(nums[i] - nums[j]) for i < j < k. maxVal = Math.max(maxVal, (long)max_ij * num); // Current num is nums[j]. max_i is max(nums[i]) for i < j. max_ij = Math.max(max_ij, max_i - num); // Current num is nums[i]. Update max_i for future iterations. max_i = Math.max(max_i, num); } return maxVal; }}Complexity
Time
O(n), as we iterate through the array only once.
Space
O(1), as we only use a few variables to store the running maximums.
Trade-offs
Pros
Most efficient solution with O(n) time and O(1) space.
Processes the array in a single pass.
Cons
The logic can be less intuitive to grasp compared to more direct approaches.
The most straightforward solution is to exhaustively check every possible ordered triplet (i, j, k) where i < j < k. We can use three nested loops to iterate through all combinations of indices, calculate the value (nums[i] - nums[j]) * nums[k] for each, and keep track of the maximum value found. Since the problem asks for 0 if the maximum value is negative, initializing our result to 0 handles this case.
Algorithm
- Initialize a variable
maxValto 0. - Use three nested loops to iterate through all possible ordered triplets of indices
(i, j, k)such thati < j < k. - For each triplet, calculate the value
currentVal = (long)(nums[i] - nums[j]) * nums[k]. - Update
maxValby taking the maximum ofmaxValandcurrentVal. - After checking all triplets, return
maxVal.
Walkthrough
This approach directly translates the problem statement into code. We set up three nested loops to generate all valid index triplets (i, j, k).
- The outer loop iterates
ifrom0ton-3. - The middle loop iterates
jfromi+1ton-2. - The inner loop iterates
kfromj+1ton-1.
Inside the innermost loop, we have a valid triplet. We calculate its value, ensuring we use a long type to prevent potential integer overflow. We then compare this value with our running maximum and update it if the new value is greater. This process guarantees that we check every single possibility and find the global maximum.
class Solution { public long maximumValue(int[] nums) { long maxVal = 0; int n = nums.length; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { long currentVal = (long)(nums[i] - nums[j]) * nums[k]; if (currentVal > maxVal) { maxVal = currentVal; } } } } return maxVal; }}Complexity
Time
O(n³), where n is the length of `nums`. We have three nested loops, each potentially iterating up to `n` times, leading to a cubic relationship with the input size.
Space
O(1), as we only use a few variables to store the indices and the maximum value, regardless of the input size.
Trade-offs
Pros
Simple to understand and implement.
Correctly solves the problem by exploring the entire search space.
Cons
Highly inefficient due to its cubic time complexity.
Will be too slow for larger input sizes (though it passes for the given constraints).
We can improve upon the brute-force approach by making a key observation. For a fixed middle index j, to maximize the expression (nums[i] - nums[j]) * nums[k], we need to maximize the term (nums[i] - nums[j]) and the term nums[k] independently. Since nums[k] is always positive, this means we should find the largest possible nums[i] for i < j and the largest possible nums[k] for k > j. This insight allows us to reduce the number of loops from three to two.
Algorithm
- Initialize
maxVal = 0. - Iterate through each possible middle index
jfrom1ton-2. - For each
j, find the maximum element in the prefixnums[0...j-1], let's call itmax_i_val. - For the same
j, find the maximum element in the suffixnums[j+1...n-1], let's call itmax_k_val. - If
max_i_val > nums[j], calculate the potential maximum value ascurrentVal = (long)(max_i_val - nums[j]) * max_k_val. - Update
maxVal = max(maxVal, currentVal). - Return
maxVal.
Walkthrough
Instead of three nested loops, we can iterate with a single main loop for the middle index j. For each j, we then perform two separate searches:
- A search for the maximum value in the subarray to the left of
j(nums[0...j-1]). - A search for the maximum value in the subarray to the right of
j(nums[j+1...n-1]).
Once we have these two maximums (max_i_val and max_k_val), we can calculate the best possible triplet value for that specific j. We update our global maximum with this value and continue the process for all possible j's.
class Solution { public long maximumValue(int[] nums) { long maxVal = 0; int n = nums.length; for (int j = 1; j < n - 1; j++) { int max_i = 0; for (int i = 0; i < j; i++) { if (nums[i] > max_i) { max_i = nums[i]; } } if (max_i > nums[j]) { int max_k = 0; for (int k = j + 1; k < n; k++) { if (nums[k] > max_k) { max_k = nums[k]; } } long currentVal = (long)(max_i - nums[j]) * max_k; if (currentVal > maxVal) { maxVal = currentVal; } } } return maxVal; }}Complexity
Time
O(n²). The main loop for `j` runs `n-2` times. Inside this loop, finding `max_i_val` takes O(j) time and finding `max_k_val` takes O(n-j) time. The total work for each `j` is O(n), leading to an overall complexity of O(n²).
Space
O(1), as we only use a constant number of variables.
Trade-offs
Pros
More efficient than the triple loop brute-force approach.
The logic is a direct optimization based on the structure of the expression.
Cons
Still inefficient for large inputs.
Involves redundant calculations, as the prefix and suffix maximums are re-calculated from scratch for each
j.
The O(n²) approach can be further optimized by eliminating the repeated computations of prefix and suffix maximums. We can precompute these values once and store them in auxiliary arrays. This allows us to find the required maximums for any middle index j in constant time, leading to a linear time solution.
Algorithm
- Create a
prefixMaxarray whereprefixMax[i]storesmax(nums[0...i]). - Create a
suffixMaxarray wheresuffixMax[i]storesmax(nums[i...n-1]). - Initialize
maxVal = 0. - Iterate
jfrom1ton-2. - For each
j, the maximumnums[i]fori < jisprefixMax[j-1]. - The maximum
nums[k]fork > jissuffixMax[j+1]. - Calculate
currentVal = (long)(prefixMax[j-1] - nums[j]) * suffixMax[j+1]. - Update
maxVal = max(maxVal, currentVal). - Return
maxVal.
Walkthrough
This approach consists of three main steps:
- Prefix Maximums: Create an array
prefixMaxof the same size asnums. Traversenumsfrom left to right, fillingprefixMaxsuch thatprefixMax[i]holds the maximum value found innumsfrom index0up toi. - Suffix Maximums: Create another array
suffixMax. Traversenumsfrom right to left, fillingsuffixMaxsuch thatsuffixMax[i]holds the maximum value from indexito the end of the array. - Final Calculation: Iterate through the middle index
jfrom1ton-2. For eachj, the maximumnums[i](withi < j) isprefixMax[j-1]and the maximumnums[k](withk > j) issuffixMax[j+1]. We can now calculate the triplet value in O(1) and update the overall maximum.
class Solution { public long maximumValue(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 maxVal = 0; for (int j = 1; j < n - 1; j++) { long val_i = prefixMax[j - 1]; long val_j = nums[j]; long val_k = suffixMax[j + 1]; if (val_i > val_j) { long currentVal = (val_i - val_j) * val_k; if (currentVal > maxVal) { maxVal = currentVal; } } } return maxVal; }}Complexity
Time
O(n). We have three separate loops, each running `n` times (one for prefix max, one for suffix max, one for the final calculation). The total time is O(n) + O(n) + O(n) = O(n).
Space
O(n) for the `prefixMax` and `suffixMax` arrays.
Trade-offs
Pros
Achieves an efficient linear time complexity.
The logic is a clear trade-off between space and time.
Cons
Requires extra space proportional to the input size.
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.