Maximum Value of an Ordered Triplet II

Problem

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

Examples

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 <= 10^5
• 1 <= nums[i] <= 10^6

Solution

Method 1 - Maintain the maximums

Here is the approach:

1. For a valid triplet (i, j, k) where i < j < k, the formula (nums[i] - nums[j]) * nums[k] can be divided into parts:
   • Part 1: nums[i] and nums[j], which contribute to the difference nums[i] - nums[j].
   • Part 2: nums[k], which multiplies the result of nums[i] - nums[j].
2. Precomputations:
   • Maintain a running maximum of nums[i] for all i while traversing to index j.
   • Calculate nums[i] - nums[j] efficiently by subtracting the running maximum nums[i] from nums[j].
   • Similarly, keep track of the maximum value of nums[k] as you traverse the array forward.
3. Single Pass Traversal:
   • Compute nums[i] - nums[j] using the precomputed running maximum nums[i].
   • Multiply with the maximum value of nums[k].
   • Maintain the global maximum value in a single traversal.

Code

Java

class Solution {
    public long maximumTripletValue(int[] nums) {
        int n = nums.length;
        long ans = 0;

        // Track the maximum value of nums[i] while traversing
        int max_i = nums[0];

        // Iterate through the array to find the maximum value of the triplet
        for (int j = 1; j < n - 1; j++) {  // `j` must be the second element, avoiding edges
            // Find max `nums[k]` from `(j + 1) to (n - 1)`
            int max_k = nums[j + 1];
            for (int k = j + 2; k < n; k++) {
                max_k = Math.max(max_k, nums[k]);
            }

            // Compute the triplet value using precomputed values
            long triplet_val = (long) (max_i - nums[j]) * max_k;

            // Update the maximum triplet value
            ans = Math.max(ans, triplet_val);

            // Update the running maximum for `nums[i]`
            max_i = Math.max(max_i, nums[j]);
        }

        return ans;
    }
}

Python

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n: int = len(nums)
        ans: int = 0

        # Track the maximum value of nums[i] while traversing
        max_i: int = nums[0]
        
        # Iterate through the array to find the maximum value of the triplet
        for j in range(1, n - 1):  # `j` must be the second element, avoiding edges
            max_k: int = max(nums[j + 1:])  # Find max `nums[k]` from `(j + 1) to (n - 1)`
            
            # Compute the triplet value using precomputed values
            triplet_val: int = (max_i - nums[j]) * max_k
            
            # Update the maximum triplet value
            ans = max(ans, triplet_val)

            # Update the running maximum for `nums[i]`
            max_i = max(max_i, nums[j])

        return ans

Complexity

• ⏰ Time complexity: O(n^2)
• 🧺 Space complexity: O(1)

Method 2 - Using Suffix and Prefix

To achieve an O(n) solution, we need to optimise the tracking and calculation of values such that we do not perform repetitive work for precomputations like maximum values. The key idea here is to make use of prefix maximums for nums[i] and suffix maximums for nums[k] in a single traversal.

Key Insights

1. Break the formula (nums[i] - nums[j]) * nums[k] into:
   • Prefix Values: For each j, calculate the maximum of nums[i] for all i < j.
   • Suffix Values: For each j, calculate the maximum of nums[k] for all k > j.
2. Traverse the array once to compute prefix maximums.
3. Traverse the array again, in reverse, to compute suffix maximums.
4. With this precomputation, iterate through j (middle element of the triplet) and calculate the triplet value in constant time.

Steps in the Algorithm

1. Prefix Maximums:
   • Compute an array prefix_max where prefix_max[j] stores the maximum value of nums[i] for all indices i < j.
2. Suffix Maximums:
   • Compute an array suffix_max where suffix_max[j] stores the maximum value of nums[k] for all indices k > j.
3. Triplet Calculation:
   • Iterate over j and compute (prefix_max[j] - nums[j]) * suffix_max[j] for each valid j.
   • Maintain a global maximum result.

Code

Java

class Solution {
    public long maximumTripletValue(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return 0; // Need at least 3 elements for a valid triplet
        }
        
        // Step 1: Compute prefix maximums
        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]);
        }
        
        // Step 2: Compute suffix maximums
        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]);
        }
        
        // Step 3: Calculate maximum triplet value
        long ans = 0;
        for (int j = 1; j < n - 1; j++) { // 'j' must be the middle element
            long tripletValue = (long) (prefixMax[j - 1] - nums[j]) * suffixMax[j + 1];
            ans = Math.max(ans, tripletValue);
        }
        
        return ans;
    }
}

Python

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n: int = len(nums)
        if n < 3:
            return 0  # Need at least 3 elements for a valid triplet
        
        # Step 1: Compute prefix maximums
        prefix_max = [0] * n
        prefix_max[0] = nums[0]
        for i in range(1, n):
            prefix_max[i] = max(prefix_max[i - 1], nums[i])
        
        # Step 2: Compute suffix maximums
        suffix_max = [0] * n
        suffix_max[n - 1] = nums[n - 1]
        for i in range(n - 2, -1, -1):
            suffix_max[i] = max(suffix_max[i + 1], nums[i])
        
        # Step 3: Calculate maximum triplet value
        ans: int = 0
        for j in range(1, n - 1):  # 'j' must be the middle element
            triplet_val: int = (prefix_max[j - 1] - nums[j]) * suffix_max[j + 1]
            ans = max(ans, triplet_val)
        
        return ans

Complexity

• ⏰ Time complexity: O(n). The prefix and suffix computations and the final triplet calculations each take linear time.
• 🧺 Space complexity: O(1). Two additional arrays (prefix_max and suffix_max) of size n are used.