Maximum Increasing Triplet Value solution and explanation
The problem
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] <= 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.
class Solution:
def maximumTripletValue(self, nums: List[int]) -> int:
n = len(nums)
right = [nums[-1]] * n
for i in range(n - 2, -1, -1):
right[i] = max(nums[i], right[i + 1])
sl = SortedList([nums[0]])
ans = 0
for j in range(1, n - 1):
if right[j + 1] > nums[j]:
i = sl.bisect_left(nums[j]) - 1
if i >= 0:
ans = max(ans, sl[i] - nums[j] + right[j + 1])
sl.add(nums[j])
return ansclass Solution {
public int maximumTripletValue(int[] nums) {
int n = nums.length;
int[] right = new int[n];
right[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; --i) {
right[i] = Math.max(nums[i], right[i + 1]);
}
TreeSet<Integer> ts = new TreeSet<>();
ts.add(nums[0]);
int ans = 0;
for (int j = 1; j < n - 1; ++j) {
if (right[j + 1] > nums[j]) {
Integer it = ts.lower(nums[j]);
if (it != null) {
ans = Math.max(ans, it - nums[j] + right[j + 1]);
}
}
ts.add(nums[j]);
}
return ans;
}
}class Solution {
public:
int maximumTripletValue(vector<int>& nums) {
int n = nums.size();
vector<int> right(n, nums.back());
for (int i = n - 2; ~i; --i) {
right[i] = max(nums[i], right[i + 1]);
}
set<int> ts;
ts.insert(nums[0]);
int ans = 0;
for (int j = 1; j < n - 1; ++j) {
if (right[j + 1] > nums[j]) {
auto it = ts.lower_bound(nums[j]);
if (it != ts.begin()) {
--it;
ans = max(ans, *it - nums[j] + right[j + 1]);
}
}
ts.insert(nums[j]);
}
return ans;
}
};function maximumTripletValue(nums: number[]): number {
const n = nums.length;
const right: number[] = Array(n).fill(nums[n - 1]);
for (let i = n - 2; ~i; --i) {
right[i] = Math.max(nums[i], right[i + 1]);
}
const ts = new TreeSet<number>();
ts.add(nums[0]);
let ans = 0;
for (let j = 1; j < n - 1; ++j) {
if (right[j + 1] > nums[j]) {
const val = ts.lower(nums[j]);
if (val !== undefined) {
ans = Math.max(ans, val - nums[j] + right[j + 1]);
}
}
ts.add(nums[j]);
}
return ans;
}
type Compare<T> = (lhs: T, rhs: T) => number;
class RBTreeNode<T = number> {
data: T;
count: number;
left: RBTreeNode<T> | null;
right: RBTreeNode<T> | null;
parent: RBTreeNode<T> | null;
color: number;
constructor(data: T) {
this.data = data;
this.left = this.right = this.parent = null;
this.color = 0;
this.count = 1;
}
sibling(): RBTreeNode<T> | null {
if (!this.parent) return null; // sibling null if no parent
return this.isOnLeft() ? this.parent.right : this.parent.left;
}
isOnLeft(): boolean {
return this === this.parent!.left;
}
hasRedChild(): boolean {
return (
Boolean(this.left && this.left.color === 0) ||
Boolean(this.right && this.right.color === 0)
);
}
}
class RBTree<T> {
root: RBTreeNode<T> | null;
lt: (l: T, r: T) => boolean;
constructor(compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0)) {
this.root = null;
this.lt = (l: T, r: T) => compare(l, r) < 0;
}
rotateLeft(pt: RBTreeNode<T>): void {
const right = pt.right!;
pt.right = right.left;
if (pt.right) pt.right.parent = pt;
right.parent = pt.parent;
if (!pt.parent) this.root = right;
else if (pt === pt.parent.left) pt.parent.left = right;
else pt.parent.right = right;
right.left = pt;
pt.parent = right;
}
rotateRight(pt: RBTreeNode<T>): void {
const left = pt.left!;
pt.left = left.right;
if (pt.left) pt.left.parent = pt;
left.parent = pt.parent;
if (!pt.parent) this.root = left;
else if (pt === pt.parent.left) pt.parent.left = left;
else pt.parent.right = left;
left.right = pt;
pt.parent = left;
}
swapColor(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
const tmp = p1.color;
p1.color = p2.color;
p2.color = tmp;
}
swapData(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
const tmp = p1.data;
p1.data = p2.data;
p2.data = tmp;
}
fixAfterInsert(pt: RBTreeNode<T>): void {
let parent = null;
let grandParent = null;
while (pt !== this.root && pt.color !== 1 && pt.parent?.color === 0) {
parent = pt.parent;
grandParent = pt.parent.parent;
/* Case : A
Parent of pt is left child of Grand-parent of pt */
if (parent === grandParent?.left) {
const uncle = grandParent.right;
/* Case : 1
The uncle of pt is also red
Only Recoloring required */
if (uncle && uncle.color === 0) {
grandParent.color = 0;
parent.color = 1;
uncle.color = 1;
pt = grandParent;
} else {
/* Case : 2
pt is right child of its parent
Left-rotation required */
if (pt === parent.right) {
this.rotateLeft(parent);
pt = parent;
parent = pt.parent;
}
/* Case : 3
pt is left child of its parent
Right-rotation required */
this.rotateRight(grandParent);
this.swapColor(parent!, grandParent);
pt = parent!;
}
} else {
/* Case : B
Parent of pt is right child of Grand-parent of pt */
const uncle = grandParent!.left;
/* Case : 1
The uncle of pt is also red
Only Recoloring required */
if (uncle != null && uncle.color === 0) {
grandParent!.color = 0;
parent.color = 1;
uncle.color = 1;
pt = grandParent!;
} else {
/* Case : 2
pt is left child of its parent
Right-rotation required */
if (pt === parent.left) {
this.rotateRight(parent);
pt = parent;
parent = pt.parent;
}
/* Case : 3
pt is right child of its parent
Left-rotation required */
this.rotateLeft(grandParent!);
this.swapColor(parent!, grandParent!);
pt = parent!;
}
}
}
this.root!.color = 1;
}
delete(val: T): boolean {
const node = this.find(val);
if (!node) return false;
node.count--;
if (!node.count) this.deleteNode(node);
return true;
}
deleteAll(val: T): boolean {
const node = this.find(val);
if (!node) return false;
this.deleteNode(node);
return true;
}
deleteNode(v: RBTreeNode<T>): void {
const u = BSTreplace(v);
// True when u and v are both black
const uvBlack = (u === null || u.color === 1) && v.color === 1;
const parent = v.parent!;
if (!u) {
// u is null therefore v is leaf
if (v === this.root) this.root = null;
// v is root, making root null
else {
if (uvBlack) {
// u and v both black
// v is leaf, fix double black at v
this.fixDoubleBlack(v);
} else {
// u or v is red
if (v.sibling()) {
// sibling is not null, make it red"
v.sibling()!.color = 0;
}
}
// delete v from the tree
if (v.isOnLeft()) parent.left = null;
else parent.right = null;
}
return;
}
if (!v.left || !v.right) {
// v has 1 child
if (v === this.root) {
// v is root, assign the value of u to v, and delete u
v.data = u.data;
v.left = v.right = null;
} else {
// Detach v from tree and move u up
if (v.isOnLeft()) parent.left = u;
else parent.right = u;
u.parent = parent;
if (uvBlack) this.fixDoubleBlack(u);
// u and v both black, fix double black at u
else u.color = 1; // u or v red, color u black
}
return;
}
// v has 2 children, swap data with successor and recurse
this.swapData(u, v);
this.deleteNode(u);
// find node that replaces a deleted node in BST
function BSTreplace(x: RBTreeNode<T>): RBTreeNode<T> | null {
// when node have 2 children
if (x.left && x.right) return successor(x.right);
// when leaf
if (!x.left && !x.right) return null;
// when single child
return x.left ?? x.right;
}
// find node that do not have a left child
// in the subtree of the given node
function successor(x: RBTreeNode<T>): RBTreeNode<T> {
let temp = x;
while (temp.left) temp = temp.left;
return temp;
}
}
fixDoubleBlack(x: RBTreeNode<T>): void {
if (x === this.root) return; // Reached root
const sibling = x.sibling();
const parent = x.parent!;
if (!sibling) {
// No sibiling, double black pushed up
this.fixDoubleBlack(parent);
} else {
if (sibling.color === 0) {
// Sibling red
parent.color = 0;
sibling.color = 1;
if (sibling.isOnLeft()) this.rotateRight(parent);
// left case
else this.rotateLeft(parent); // right case
this.fixDoubleBlack(x);
} else {
// Sibling black
if (sibling.hasRedChild()) {
// at least 1 red children
if (sibling.left && sibling.left.color === 0) {
if (sibling.isOnLeft()) {
// left left
sibling.left.color = sibling.color;
sibling.color = parent.color;
this.rotateRight(parent);
} else {
// right left
sibling.left.color = parent.color;
this.rotateRight(sibling);
this.rotateLeft(parent);
}
} else {
if (sibling.isOnLeft()) {
// left right
sibling.right!.color = parent.color;
this.rotateLeft(sibling);
this.rotateRight(parent);
} else {
// right right
sibling.right!.color = sibling.color;
sibling.color = parent.color;
this.rotateLeft(parent);
}
}
parent.color = 1;
} else {
// 2 black children
sibling.color = 0;
if (parent.color === 1) this.fixDoubleBlack(parent);
else parent.color = 1;
}
}
}
}
insert(data: T): boolean {
// search for a position to insert
let parent = this.root;
while (parent) {
if (this.lt(data, parent.data)) {
if (!parent.left) break;
else parent = parent.left;
} else if (this.lt(parent.data, data)) {
if (!parent.right) break;
else parent = parent.right;
} else break;
}
// insert node into parent
const node = new RBTreeNode(data);
if (!parent) this.root = node;
else if (this.lt(node.data, parent.data)) parent.left = node;
else if (this.lt(parent.data, node.data)) parent.right = node;
else {
parent.count++;
return false;
}
node.parent = parent;
this.fixAfterInsert(node);
return true;
}
find(data: T): RBTreeNode<T> | null {
let p = this.root;
while (p) {
if (this.lt(data, p.data)) {
p = p.left;
} else if (this.lt(p.data, data)) {
p = p.right;
} else break;
}
return p ?? null;
}
*inOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
if (!root) return;
for (const v of this.inOrder(root.left!)) yield v;
yield root.data;
for (const v of this.inOrder(root.right!)) yield v;
}
*reverseInOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
if (!root) return;
for (const v of this.reverseInOrder(root.right!)) yield v;
yield root.data;
for (const v of this.reverseInOrder(root.left!)) yield v;
}
}
class TreeSet<T = number> {
_size: number;
tree: RBTree<T>;
compare: Compare<T>;
constructor(
collection: T[] | Compare<T> = [],
compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0),
) {
if (typeof collection === 'function') {
compare = collection;
collection = [];
}
this._size = 0;
this.compare = compare;
this.tree = new RBTree(compare);
for (const val of collection) this.add(val);
}
size(): number {
return this._size;
}
has(val: T): boolean {
return !!this.tree.find(val);
}
add(val: T): boolean {
const successful = this.tree.insert(val);
this._size += successful ? 1 : 0;
return successful;
}
delete(val: T): boolean {
const deleted = this.tree.deleteAll(val);
this._size -= deleted ? 1 : 0;
return deleted;
}
ceil(val: T): T | undefined {
let p = this.tree.root;
let higher = null;
while (p) {
if (this.compare(p.data, val) >= 0) {
higher = p;
p = p.left;
} else {
p = p.right;
}
}
return higher?.data;
}
floor(val: T): T | undefined {
let p = this.tree.root;
let lower = null;
while (p) {
if (this.compare(val, p.data) >= 0) {
lower = p;
p = p.right;
} else {
p = p.left;
}
}
return lower?.data;
}
higher(val: T): T | undefined {
let p = this.tree.root;
let higher = null;
while (p) {
if (this.compare(val, p.data) < 0) {
higher = p;
p = p.left;
} else {
p = p.right;
}
}
return higher?.data;
}
lower(val: T): T | undefined {
let p = this.tree.root;
let lower = null;
while (p) {
if (this.compare(p.data, val) < 0) {
lower = p;
p = p.right;
} else {
p = p.left;
}
}
return lower?.data;
}
first(): T | undefined {
return this.tree.inOrder().next().value;
}
last(): T | undefined {
return this.tree.reverseInOrder().next().value;
}
shift(): T | undefined {
const first = this.first();
if (first === undefined) return undefined;
this.delete(first);
return first;
}
pop(): T | undefined {
const last = this.last();
if (last === undefined) return undefined;
this.delete(last);
return last;
}
*[Symbol.iterator](): Generator<T, void, void> {
for (const val of this.values()) yield val;
}
*keys(): Generator<T, void, void> {
for (const val of this.values()) yield val;
}
*values(): Generator<T, undefined, void> {
for (const val of this.tree.inOrder()) yield val;
return undefined;
}
/**
* Return a generator for reverse order traversing the set
*/
*rvalues(): Generator<T, undefined, void> {
for (const val of this.tree.reverseInOrder()) yield val;
return undefined;
}
}func maximumTripletValue(nums []int) (ans int) {
n := len(nums)
right := make([]int, n)
right[n-1] = nums[n-1]
for i := n - 2; i >= 0; i-- {
right[i] = max(nums[i], right[i+1])
}
ts := treemap.NewWithIntComparator()
ts.Put(nums[0], nil)
for j := 1; j < n-1; j++ {
if right[j+1] > nums[j] {
val, _ := ts.Floor(nums[j] - 1)
if val != nil {
ans = max(ans, val.(int)-nums[j]+right[j+1])
}
}
ts.Put(nums[j], nil)
}
return
}Complexity analysis
| 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 |
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).