Given an array nums, return the maximum value of a triplet (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k].
The value of a triplet (i, j, k) is nums[i] - nums[j] + nums[k].
Example 1:
Input: nums = [5,6,9]
Output: 8
Explanation: We only have one choice for an increasing triplet and that is choosing all three elements. The value of this triplet would be 5 - 6 + 9 = 8.
Example 2:
Input: nums = [1,5,3,6]
Output: 4
Explanation: There are only two increasing triplets:
(0, 1, 3): The value of this triplet is nums[0] - nums[1] + nums[3] = 1 - 5 + 6 = 2.
(0, 2, 3): The value of this triplet is nums[0] - nums[2] + nums[3] = 1 - 3 + 6 = 4.
Thus the answer would be 4.
Constraints:
3 <= nums.length <= 1051 <= nums[i] <= 109Problem Overview: Given an array nums, choose indices i < j < k such that nums[i] < nums[j] < nums[k]. For every valid increasing triplet, compute the defined triplet value and return the maximum possible result. The challenge is efficiently finding the best candidate on both sides of the middle index j.
Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)
The most direct strategy checks every possible triplet. Use three nested loops for i, j, and k while enforcing i < j < k. For each combination, verify the increasing condition nums[i] < nums[j] < nums[k] and compute the triplet value. Track the maximum across all valid triplets. This approach is simple and useful for validating correctness, but the O(n^3) time complexity becomes infeasible once the array grows beyond a few hundred elements.
Approach 2: Suffix Maximum + Ordered Set (O(n log n) time, O(n) space)
A more efficient method treats each index j as the middle element of the triplet. The goal becomes finding the best valid i to the left and the best k to the right. Precompute a suffix array where suffixMax[j] stores the largest value to the right of j. This allows constant-time lookup of the best candidate for k.
For the left side, maintain an ordered set (balanced BST) containing values already seen while scanning from left to right. Using operations like lower_bound or predecessor search, you can quickly find the largest number strictly smaller than nums[j]. That element becomes the best candidate for index i. If both a valid predecessor and a valid suffix maximum exist, compute the triplet value and update the answer.
The ordered structure guarantees O(log n) insertion and lookup, producing an overall O(n log n) algorithm. This pattern combines ideas from array scanning, suffix preprocessing, and balanced trees such as ordered sets or TreeSet. It is a common technique when a problem requires "best element smaller than X on the left" and "best element on the right" at the same time.
Recommended for interviews: Start by explaining the brute force approach to demonstrate understanding of the constraints and the increasing-triplet condition. Then move to the optimized method using a suffix maximum array and an ordered set. Interviewers expect the O(n log n) solution because it shows you can combine array preprocessing with efficient ordered lookups instead of repeatedly scanning the array.
We can consider enumerating nums[j]. Then, we need to find the largest nums[i] on the left of j such that nums[i] < nums[j], and find the largest nums[k] on the right of j such that nums[k] > nums[j].
Therefore, we can preprocess an array right, where right[i] represents the maximum value to the right of nums[i]. Then, we can use an ordered set to maintain the values on the left of nums[j], so that we can find the largest nums[i] less than nums[j] in O(log n) time.
The time complexity is O(n times log n), and the space complexity is O(n), where n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Triplet Enumeration | O(n^3) | O(1) | Useful for understanding the problem or verifying correctness on very small inputs |
| Suffix Maximum + Ordered Set | O(n log n) | O(n) | General optimal solution when you must efficiently track a smaller element on the left and the best candidate on the right |
3073. Maximum Increasing Triplet Value (Leetcode Medium) • Programming Live with Larry • 260 views views
Practice Maximum Increasing Triplet Value with our built-in code editor and test cases.
Practice on FleetCode