Problem Informations

• Problem Index: 2874
• Problem Link: Maximum Value of an Ordered Triplet II
• Topics: Array

Problem Description

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 $(\text{nums}[i] - \text{nums}[j]) \times \text{nums}[k]$.

Example 1:

Input: nums = [12,6,1,2,7]
Output: 77
Explanation: The value of the triplet (0, 2, 4) is $(\text{nums}[0] - \text{nums}[2]) \times \text{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 $(\text{nums}[1] - \text{nums}[2]) \times \text{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 $(\text{nums}[0] - \text{nums}[1]) \times \text{nums}[2] = -3$. Hence, the answer would be 0.

Constraints:

• $3 \leq \text{nums.length} \leq 10^5$
• $1 \leq \text{nums}[i] \leq 10^6$

Intuition

The problem requires us to find the maximum value over all triplets of indices $(i, j, k)$ in the array nums such that $i < j < k$. The critical insight is understanding the nature of the triplet value, defined as $(\text{nums}[i] - \text{nums}[j]) \times \text{nums}[k]$. This equation has two components: a difference $(\text{nums}[i] - \text{nums}[j])$, which is maximized when the first number is much larger than the second, and a multiplier $\text{nums}[k]$, which should be as large as possible. Our strategy involves preprocessing potential maximum values and differences as we iterate through the array to efficiently compute this triplet value.

Approach

The approach to solving this problem is to use a single pass (O(n) time complexity) to calculate the maximum triplet values dynamically:

1. Initialization: Begin by initializing the variable answer to store the maximum triplet value found so far as zero. Also, set up two other key variables: max_val, which stores the maximum value between the first two elements, and diff, initialized to the difference between the first two elements ($\text{nums}[0] - \text{nums}[1]$).

2. Iterative Computation: Iterate through the array starting from the third element (index 2).

   • Triplet Value Calculation: For each new element (as $\text{nums}[k]$), calculate the triplet value using the precomputed diff as $(\text{nums}[i] - \text{nums}[j]) \times \text{nums}[k]$. Update answer with the maximum of its current value and the newly calculated triplet value.
   • Update Difference: Simultaneously, maintain the best possible diff for future iterations. This involves updating diff to be the maximum of its current value or the difference between max_val and the current element $\text{nums}[i]$.
   • Update Maximum Value: Update max_val to be the maximum of itself and the current element $\text{nums}[i]$, ensuring it represents the largest value encountered so far for potential future i indices.

3. Result: By the end of the iteration, answer contains the maximum triplet value; return this value as the final output.

This approach effectively builds on the intuition that precalculating the best possible differences and keeping track of the maximum values as we iterate allows us to intelligently and efficiently evaluate potential triplet combinations. If all such evaluated triplet values are negative, the initialized value of zero for answer remains unchanged, ensuring compliance with the problem’s conditions.

Code

C++

class Solution {
public:
    // Function to return the maximum of two long long integers
    long long max(long long a, long long b) { 
        return a > b ? a : b; 
    }
    
    // Function to find the maximum triplet value according to the given condition
    long long maximumTripletValue(vector<int>& nums) {
        // Initialize the answer and calculate initial values for max_val and diff
        long long answer = 0;
        long long max_val = max(nums[0], nums[1]);
        long long diff = nums[0] - nums[1];

        // Iterate through the nums array starting from the third element
        for (int i = 2; i < nums.size(); i++) {
            // Update the answer by checking the current triplet value
            answer = max(answer, diff * nums[i]);
            // Update the diff for the next potential triplet
            diff = max(diff, max_val - nums[i]);
            // Update max_val for future calculations
            max_val = max(max_val, nums[i]);
        }

        // Return the maximum triplet value computed
        return answer;
    }
};

Python

class Solution:
    # Function to return the maximum of two integers
    def max(self, a, b):
        return a if a > b else b

    # Function to find the maximum triplet value according to the given condition
    def maximumTripletValue(self, nums):
        # Initialize the answer and calculate initial values for max_val and diff
        answer = 0
        max_val = self.max(nums[0], nums[1])
        diff = nums[0] - nums[1]

        # Iterate through the nums array starting from the third element
        for i in range(2, len(nums)):
            # Update the answer by checking the current triplet value
            answer = self.max(answer, diff * nums[i])
            # Update the diff for the next potential triplet
            diff = self.max(diff, max_val - nums[i])
            # Update max_val for future calculations
            max_val = self.max(max_val, nums[i])

        # Return the maximum triplet value computed
        return answer

Complexity

• Time complexity: $O(n)$

  The time complexity of the algorithm is $O(n)$, where $n$ is the length of the nums array. This is because the function iterates over the nums array only once, starting from the third element (index 2) to the end. Each iteration involves constant-time operations such as updating variables and calling the max function (which operates in constant time since it involves just a comparison).

• Space complexity: $O(1)$

  The space complexity of the algorithm is $O(1)$ because it uses a fixed amount of extra space regardless of the input size. The algorithm only requires space for a few variables, namely answer, max_val, and diff, which store integer/computed values. No additional data structures are used that grow with the input size.