Scale Engineer

Maximum Value of an Ordered Triplet I

Easy
#2570Time: 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.1 company
Data structures
Array
Companies
Media.net

Prompt

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 <= 100
  • 1 <= 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, and max_ij = 0.
  • max_i will track the maximum nums[i] seen so far.
  • max_ij will track the maximum nums[i] - nums[j] seen so far.
  • Iterate through each num in the nums array.
  • In each iteration, first update the result: maxVal = max(maxVal, (long)max_ij * num). Here, num acts as nums[k].
  • Then, update the maximum difference: max_ij = max(max_ij, max_i - num). Here, num acts as nums[j].
  • Finally, update the maximum prefix value: max_i = max(max_i, num). Here, num acts as nums[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 potential nums[i]).
  • max_ij: The maximum difference nums[i] - nums[j] seen so far.

For each number num in the array, we perform three updates in a specific order:

  1. Treat num as nums[k]: We calculate a potential answer by multiplying num with the best (nums[i] - nums[j]) difference (max_ij) found among the elements before num. We update our overall maxVal with this result.
  2. Treat num as nums[j]: We update max_ij. A new, larger difference might be formed by using num as nums[j] and the largest element seen before it (max_i) as nums[i]. So we update max_ij = max(max_ij, max_i - num).
  3. Treat num as nums[i]: We update max_i by comparing it with the current num. This ensures max_i is ready for future elements to use as their potential nums[j] or nums[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.

Solutions

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;  }}

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

← Previous

Previous problem

Next →

Next problem