Skip to main content
Talentd

Maximum Increasing Triplet Value - Solution & Explanation

MediumPremiumFree on FleetCodeArrayOrdered Set15 min readAsked at: Uber
Practice this problem

Problem Statement

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 <= 105
  • 1 <= nums[i] <= 109
  • The input is generated such that at least one triplet meets the given condition.

Approach Overview

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

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Triplet EnumerationO(n^3)O(1)Useful for understanding the problem or verifying correctness on very small inputs
Suffix Maximum + Ordered SetO(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

Video Solution

3073. Maximum Increasing Triplet Value (Leetcode Medium) • Programming Live with Larry • 265 views views

Frequently Asked Questions

Is Maximum Increasing Triplet Value easy or hard?
Maximum Increasing Triplet Value is generally classified as a medium difficulty problem. The logic becomes straightforward once you recognize the pattern of fixing the middle element and efficiently searching for a smaller value on the left and a larger value on the right.
Maximum Increasing Triplet Value Python/Java solution
Python solutions typically use the sortedcontainers library or bisect with a maintained sorted list to simulate an ordered set. Java solutions commonly use TreeSet for predecessor queries. C++ implementations often rely on std::set. All versions implement the same suffix maximum plus ordered-set strategy with O(n log n) complexity.
How to solve Maximum Increasing Triplet Value in O(n)?
A strict O(n) solution is difficult because the algorithm must dynamically find the closest smaller element to the left of each index. Using an ordered set or balanced tree enables efficient predecessor queries, leading to an O(n log n) solution which is considered optimal for this problem.
What is the best approach for Maximum Increasing Triplet Value?
The most efficient approach uses a suffix maximum array and an ordered set. While scanning the array, treat each index as the middle element of the triplet. Use the ordered set to find the largest value smaller than nums[j] on the left and a suffix maximum array to get the best candidate on the right. This reduces the complexity to O(n log n).
Is Maximum Increasing Triplet Value asked at Google/Amazon/Meta?
Problems involving increasing triplets, ordered lookups, and prefix or suffix preprocessing frequently appear in interviews at companies like Amazon, Google, and Meta. Variants of this problem test your ability to combine array scanning with data structures such as TreeSet, balanced BSTs, or ordered containers.
What data structure is used in Maximum Increasing Triplet Value?
The optimized solution relies on an ordered set (such as TreeSet in Java or a balanced BST structure). It allows predecessor queries to quickly find the largest value smaller than the current element. A suffix maximum array is also used to track the best candidate on the right side.
What is the time complexity of Maximum Increasing Triplet Value?
The optimal solution runs in O(n log n) time because each element is inserted into an ordered set and queried using logarithmic operations such as predecessor search. The suffix maximum preprocessing runs in O(n). Overall space complexity is O(n).

Ready to solve this problem?

Practice Maximum Increasing Triplet Value with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays