Scale Engineer

Maximum Value of an Ordered Triplet II

Med
#2571Time: 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.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 <= 105
  • 1 <= 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

  1. Initialize a variable maxValue to 0, using a long data type to prevent potential overflow.
  2. Use three nested loops to iterate through all possible combinations of indices (i, j, k) such that i < j < k.
    • The outer loop for i runs from 0 to n-3.
    • The middle loop for j runs from i+1 to n-2.
    • The inner loop for k runs from j+1 to n-1.
  3. Inside the innermost loop, calculate the value of the triplet: currentValue = (long)(nums[i] - nums[j]) * nums[k].
  4. Compare currentValue with maxValue and update maxValue if currentValue is greater: maxValue = Math.max(maxValue, currentValue).
  5. After the loops complete, maxValue will hold the maximum possible value. Since the problem asks to return 0 for negative results, and our maxValue is initialized to 0 and only updated with larger values, this condition is naturally met.
  6. 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.

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