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 <= 1051 <= nums[i] <= 106In this approach, we examine every possible triplet (i, j, k) where i < j < k. By iterating through all combinations, we calculate the value (nums[i] - nums[j]) * nums[k] for each, keeping track of the maximum value encountered.
Although simple to implement, it's inefficient for large arrays because of the O(n^3) time complexity.
The C solution initializes a variable to hold the maximum triplet value at 0, selects all triplets (i, j, k) through nested loops, calculates their values, and updates the maximum if a higher value is found.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^3), as there are three nested loops; each with a progression over the length of the array.
Space Complexity: O(1), as no extra space is used proportional to input size.
This approach leverages extra data structures to track the smallest 'j' (middle) index values and the maximum 'i' (left) index values. We optimize our evaluation by computing the possible maximum difference before computing for each 'k' value.
This method greatly reduces the number of operations necessary compared to the brute force method.
With C, we track and store the minimum middle and maximum left values as we iterate through the array. By efficiently managing these values, we reduce unnecessary loop iteration, evaluating only necessary calculations for triplet potential.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), as it iterates through the array to build the minJ and maxI arrays.
Space Complexity: O(n), due to the auxiliary arrays used.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3), as there are three nested loops; each with a progression over the length of the array. |
| Optimized Approach | Time Complexity: O(n), as it iterates through the array to build the minJ and maxI arrays. |
Maximum Value of an Ordered Triplet I - Leetcode 2873 - Python • NeetCodeIO • 8,633 views views
Watch 9 more video solutions →Practice Maximum Value of an Ordered Triplet II with our built-in code editor and test cases.
Practice on FleetCode