3073. Maximum Increasing Triplet Value 🔒
Problem Description
You are given an array nums
and need to find the maximum value of a specific expression involving three elements from the array.
The task is to find three indices (i, j, k)
where:
- The indices are in increasing order:
i < j < k
- The values at these indices are also in increasing order:
nums[i] < nums[j] < nums[k]
For such a valid triplet, calculate its value using the formula: nums[i] - nums[j] + nums[k]
Your goal is to return the maximum possible value among all valid triplets.
For example:
- In the array
[5,6,9]
, there's only one valid increasing triplet using all three elements. The value would be5 - 6 + 9 = 8
. - In the array
[1,5,3,6]
, there are two valid triplets:- Indices
(0, 1, 3)
with values(1, 5, 6)
giving1 - 5 + 6 = 2
- Indices
(0, 2, 3)
with values(1, 3, 6)
giving1 - 3 + 6 = 4
- The maximum is
4
- Indices
The problem guarantees that at least one valid triplet exists in the input array. The array length ranges from 3 to 100,000 elements, and each element can be as large as 10^9.
The key insight is that to maximize nums[i] - nums[j] + nums[k]
, you want nums[i]
to be as large as possible (while still less than nums[j]
), nums[j]
to be as small as possible (while still greater than nums[i]
and less than nums[k]
), and nums[k]
to be as large as possible (while still greater than nums[j]
).
Intuition
To maximize the expression nums[i] - nums[j] + nums[k]
, let's think about what we want from each component:
- We want
nums[i]
to be as large as possible (adds to the result) - We want
nums[j]
to be as small as possible (subtracts from the result) - We want
nums[k]
to be as large as possible (adds to the result)
But we have constraints: i < j < k
and nums[i] < nums[j] < nums[k]
.
The key insight is to fix one element and optimize the other two. If we fix nums[j]
as our middle element, then:
- We need to find the largest
nums[i]
to the left ofj
wherenums[i] < nums[j]
- We need to find the largest
nums[k]
to the right ofj
wherenums[k] > nums[j]
For finding the largest nums[k]
to the right, we can preprocess the array to store the maximum value from each position to the end. This gives us O(1) lookup for any position.
For finding the largest nums[i]
to the left that's less than nums[j]
, we need something more sophisticated. As we iterate through potential j
values, we can maintain all values to the left in a sorted structure. Then, for any nums[j]
, we can use binary search to find the largest value less than nums[j]
efficiently.
This approach works because:
- By iterating through all possible middle elements
j
, we ensure we don't miss the optimal triplet - For each
j
, we're finding the best possiblei
andk
that satisfy our constraints - The sorted structure (like
SortedList
in Python) allows us to efficiently find the bestnums[i]
in O(log n) time - The precomputed right maximum array gives us the best
nums[k]
in O(1) time
The overall time complexity becomes O(n log n) due to the sorted list operations, which is efficient even for the maximum constraint of 10^5 elements.
Solution Approach
The implementation uses a suffix maximum array combined with an ordered set to efficiently find the optimal triplet.
Step 1: Build the Suffix Maximum Array
First, we create a right
array where right[i]
stores the maximum value from index i
to the end of the array:
right = [nums[-1]] * n
for i in range(n - 2, -1, -1):
right[i] = max(nums[i], right[i + 1])
This allows us to quickly find the largest element to the right of any position in O(1) time.
Step 2: Use SortedList for Left Elements
We initialize a SortedList
with the first element:
sl = SortedList([nums[0]])
This data structure maintains elements in sorted order and supports:
- Binary search in O(log n)
- Insertion in O(log n)
Step 3: Enumerate Middle Element j
We iterate through indices from 1 to n-2 as potential middle elements j
:
for j in range(1, n - 1):
Step 4: Check if Valid k Exists
For each j
, we first check if there exists a valid k
(an element greater than nums[j]
on the right):
if right[j + 1] > nums[j]:
If true, right[j + 1]
gives us the maximum possible nums[k]
.
Step 5: Find Optimal i
We use binary search to find the largest element less than nums[j]
in our sorted list:
i = sl.bisect_left(nums[j]) - 1
bisect_left(nums[j])
returns the leftmost position wherenums[j]
would be inserted- Subtracting 1 gives us the index of the largest element less than
nums[j]
- If
i >= 0
, thensl[i]
is our optimalnums[i]
Step 6: Calculate and Update Maximum
If we found a valid i
, we calculate the triplet value:
if i >= 0:
ans = max(ans, sl[i] - nums[j] + right[j + 1])
Step 7: Add Current Element to SortedList
After processing j
, we add nums[j]
to our sorted list for future iterations:
sl.add(nums[j])
The algorithm ensures we find the maximum value by:
- Trying all possible middle elements
- For each middle element, finding the optimal left element (largest that's still smaller)
- For each middle element, using the precomputed optimal right element (largest possible)
Time Complexity: O(n log n) - dominated by SortedList operations
Space Complexity: O(n) - for the right
array and SortedList
Ready to land your dream job?
Unlock your dream job with a 5-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through the algorithm with the array nums = [2, 5, 1, 4, 8, 3]
.
Step 1: Build Suffix Maximum Array
We create the right
array where right[i]
stores the maximum value from index i
to the end:
- Starting from the end:
right[5] = 3
right[4] = max(8, 3) = 8
right[3] = max(4, 8) = 8
right[2] = max(1, 8) = 8
right[1] = max(5, 8) = 8
right[0] = max(2, 8) = 8
So right = [8, 8, 8, 8, 8, 3]
Step 2: Initialize SortedList
Start with sl = [2]
(containing nums[0]
)
Step 3-7: Iterate through middle elements
j = 1 (nums[j] = 5):
- Check if
right[2] > nums[1]
: Is8 > 5
? Yes ✓ - Find largest element in
sl
less than 5:sl = [2]
, binary search gives index 0- So
nums[i] = 2
- Calculate:
2 - 5 + 8 = 5
- Update
ans = 5
- Add 5 to sl:
sl = [2, 5]
j = 2 (nums[j] = 1):
- Check if
right[3] > nums[2]
: Is8 > 1
? Yes ✓ - Find largest element in
sl
less than 1:sl = [2, 5]
, binary search gives index -1- No valid
i
found (no element < 1)
- Add 1 to sl:
sl = [1, 2, 5]
j = 3 (nums[j] = 4):
- Check if
right[4] > nums[3]
: Is8 > 4
? Yes ✓ - Find largest element in
sl
less than 4:sl = [1, 2, 5]
, binary search gives index 1- So
nums[i] = 2
- Calculate:
2 - 4 + 8 = 6
- Update
ans = 6
- Add 4 to sl:
sl = [1, 2, 4, 5]
j = 4 (nums[j] = 8):
- Check if
right[5] > nums[4]
: Is3 > 8
? No ✗ - No valid
k
exists - Add 8 to sl:
sl = [1, 2, 4, 5, 8]
Final Result: 6
The optimal triplet is at indices (0, 3, 4) with values (2, 4, 8), giving us 2 - 4 + 8 = 6
.
Note how the algorithm efficiently found this by:
- Using the suffix max array to instantly know that 8 is available to the right of index 3
- Using binary search in the sorted list to find that 2 is the largest value less than 4 among the left elements
- Trying all possible middle elements to ensure we found the maximum
Solution Implementation
1from typing import List
2from sortedcontainers import SortedList
3
4class Solution:
5 def maximumTripletValue(self, nums: List[int]) -> int:
6 n = len(nums)
7
8 # Build array to store maximum value to the right of each position
9 # right_max[i] = maximum value from index i to the end
10 right_max = [nums[-1]] * n
11 for i in range(n - 2, -1, -1):
12 right_max[i] = max(nums[i], right_max[i + 1])
13
14 # Maintain sorted list of elements seen so far (to the left)
15 sorted_left = SortedList([nums[0]])
16 max_triplet_value = 0
17
18 # Iterate through each potential middle element (j)
19 for j in range(1, n - 1):
20 # Check if there's a larger element to the right of j
21 if right_max[j + 1] > nums[j]:
22 # Find the largest element smaller than nums[j] from the left
23 # bisect_left returns insertion position, so we need index - 1
24 left_index = sorted_left.bisect_left(nums[j]) - 1
25
26 if left_index >= 0:
27 # Calculate triplet value: nums[i] - nums[j] + nums[k]
28 # where i < j < k
29 triplet_value = sorted_left[left_index] - nums[j] + right_max[j + 1]
30 max_triplet_value = max(max_triplet_value, triplet_value)
31
32 # Add current element to sorted list for future iterations
33 sorted_left.add(nums[j])
34
35 return max_triplet_value
36
1class Solution {
2 public int maximumTripletValue(int[] nums) {
3 int n = nums.length;
4
5 // Build array to store maximum value to the right of each position
6 // maxRight[i] stores the maximum value from index i to the end
7 int[] maxRight = new int[n];
8 maxRight[n - 1] = nums[n - 1];
9 for (int i = n - 2; i >= 0; i--) {
10 maxRight[i] = Math.max(nums[i], maxRight[i + 1]);
11 }
12
13 // TreeSet to maintain sorted values seen so far (to the left of current position)
14 // This allows us to efficiently find the largest value less than nums[j]
15 TreeSet<Integer> leftValues = new TreeSet<>();
16 leftValues.add(nums[0]);
17
18 int maxTripletValue = 0;
19
20 // Iterate through potential middle elements (j position)
21 // j ranges from 1 to n-2 to ensure we have elements on both left and right
22 for (int j = 1; j < n - 1; j++) {
23 // Only consider this middle element if there's a larger element to its right
24 // This ensures nums[k] > nums[j], making the expression potentially positive
25 if (maxRight[j + 1] > nums[j]) {
26 // Find the largest element to the left that is smaller than nums[j]
27 // This maximizes nums[i] while ensuring nums[i] < nums[j]
28 Integer maxLeftSmallerValue = leftValues.lower(nums[j]);
29
30 if (maxLeftSmallerValue != null) {
31 // Calculate triplet value: nums[i] - nums[j] + nums[k]
32 int tripletValue = maxLeftSmallerValue - nums[j] + maxRight[j + 1];
33 maxTripletValue = Math.max(maxTripletValue, tripletValue);
34 }
35 }
36
37 // Add current element to the set of left values for future iterations
38 leftValues.add(nums[j]);
39 }
40
41 return maxTripletValue;
42 }
43}
44
1class Solution {
2public:
3 int maximumTripletValue(vector<int>& nums) {
4 int n = nums.size();
5
6 // Build array to store maximum value from index i to the end
7 // rightMax[i] = max(nums[i], nums[i+1], ..., nums[n-1])
8 vector<int> rightMax(n, nums.back());
9 for (int i = n - 2; i >= 0; --i) {
10 rightMax[i] = max(nums[i], rightMax[i + 1]);
11 }
12
13 // Set to maintain sorted order of elements seen so far (left side)
14 set<int> leftElements;
15 leftElements.insert(nums[0]);
16
17 int maxValue = 0;
18
19 // Iterate through middle element j of triplet (i, j, k)
20 for (int j = 1; j < n - 1; ++j) {
21 // Check if there exists a valid k > j such that nums[k] > nums[j]
22 if (rightMax[j + 1] > nums[j]) {
23 // Find the largest element less than nums[j] on the left side
24 auto it = leftElements.lower_bound(nums[j]);
25
26 // If such an element exists, calculate triplet value
27 if (it != leftElements.begin()) {
28 --it; // Move to the largest element less than nums[j]
29 // Calculate value: (nums[i] - nums[j] + nums[k])
30 int tripletValue = *it - nums[j] + rightMax[j + 1];
31 maxValue = max(maxValue, tripletValue);
32 }
33 }
34
35 // Add current element to the set of left elements
36 leftElements.insert(nums[j]);
37 }
38
39 return maxValue;
40 }
41};
42
1// Type definition for comparison function
2type Compare<T> = (lhs: T, rhs: T) => number;
3
4// Node structure for Red-Black Tree
5interface RBTreeNode<T = number> {
6 data: T;
7 count: number;
8 left: RBTreeNode<T> | null;
9 right: RBTreeNode<T> | null;
10 parent: RBTreeNode<T> | null;
11 color: number; // 0: red, 1: black
12}
13
14// Tree structure
15interface RBTree<T> {
16 root: RBTreeNode<T> | null;
17 lt: (l: T, r: T) => boolean;
18}
19
20// TreeSet structure
21interface TreeSet<T = number> {
22 size: number;
23 tree: RBTree<T>;
24 compare: Compare<T>;
25}
26
27/**
28 * Creates a new Red-Black Tree node
29 */
30function createRBTreeNode<T>(data: T): RBTreeNode<T> {
31 return {
32 data: data,
33 left: null,
34 right: null,
35 parent: null,
36 color: 0, // Red by default
37 count: 1
38 };
39}
40
41/**
42 * Gets the sibling of a node
43 */
44function getSibling<T>(node: RBTreeNode<T>): RBTreeNode<T> | null {
45 if (!node.parent) return null;
46 return isOnLeft(node) ? node.parent.right : node.parent.left;
47}
48
49/**
50 * Checks if node is left child of its parent
51 */
52function isOnLeft<T>(node: RBTreeNode<T>): boolean {
53 return node === node.parent!.left;
54}
55
56/**
57 * Checks if node has at least one red child
58 */
59function hasRedChild<T>(node: RBTreeNode<T>): boolean {
60 return (
61 Boolean(node.left && node.left.color === 0) ||
62 Boolean(node.right && node.right.color === 0)
63 );
64}
65
66/**
67 * Creates a new Red-Black Tree
68 */
69function createRBTree<T>(compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0)): RBTree<T> {
70 return {
71 root: null,
72 lt: (l: T, r: T) => compare(l, r) < 0
73 };
74}
75
76/**
77 * Performs left rotation on the tree
78 */
79function rotateLeft<T>(tree: RBTree<T>, pt: RBTreeNode<T>): void {
80 const right = pt.right!;
81 pt.right = right.left;
82
83 if (pt.right) pt.right.parent = pt;
84 right.parent = pt.parent;
85
86 if (!pt.parent) tree.root = right;
87 else if (pt === pt.parent.left) pt.parent.left = right;
88 else pt.parent.right = right;
89
90 right.left = pt;
91 pt.parent = right;
92}
93
94/**
95 * Performs right rotation on the tree
96 */
97function rotateRight<T>(tree: RBTree<T>, pt: RBTreeNode<T>): void {
98 const left = pt.left!;
99 pt.left = left.right;
100
101 if (pt.left) pt.left.parent = pt;
102 left.parent = pt.parent;
103
104 if (!pt.parent) tree.root = left;
105 else if (pt === pt.parent.left) pt.parent.left = left;
106 else pt.parent.right = left;
107
108 left.right = pt;
109 pt.parent = left;
110}
111
112/**
113 * Swaps colors of two nodes
114 */
115function swapColor<T>(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
116 const tmp = p1.color;
117 p1.color = p2.color;
118 p2.color = tmp;
119}
120
121/**
122 * Swaps data of two nodes
123 */
124function swapData<T>(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
125 const tmp = p1.data;
126 p1.data = p2.data;
127 p2.data = tmp;
128}
129
130/**
131 * Fixes Red-Black Tree properties after insertion
132 */
133function fixAfterInsert<T>(tree: RBTree<T>, pt: RBTreeNode<T>): void {
134 let parent = null;
135 let grandParent = null;
136
137 while (pt !== tree.root && pt.color !== 1 && pt.parent?.color === 0) {
138 parent = pt.parent;
139 grandParent = pt.parent.parent;
140
141 // Parent is left child of grandparent
142 if (parent === grandParent?.left) {
143 const uncle = grandParent.right;
144
145 // Uncle is red - only recoloring needed
146 if (uncle && uncle.color === 0) {
147 grandParent.color = 0;
148 parent.color = 1;
149 uncle.color = 1;
150 pt = grandParent;
151 } else {
152 // Node is right child - left rotation needed
153 if (pt === parent.right) {
154 rotateLeft(tree, parent);
155 pt = parent;
156 parent = pt.parent;
157 }
158
159 // Node is left child - right rotation needed
160 rotateRight(tree, grandParent);
161 swapColor(parent!, grandParent);
162 pt = parent!;
163 }
164 } else {
165 // Parent is right child of grandparent
166 const uncle = grandParent!.left;
167
168 // Uncle is red - only recoloring needed
169 if (uncle != null && uncle.color === 0) {
170 grandParent!.color = 0;
171 parent.color = 1;
172 uncle.color = 1;
173 pt = grandParent!;
174 } else {
175 // Node is left child - right rotation needed
176 if (pt === parent.left) {
177 rotateRight(tree, parent);
178 pt = parent;
179 parent = pt.parent;
180 }
181
182 // Node is right child - left rotation needed
183 rotateLeft(tree, grandParent!);
184 swapColor(parent!, grandParent!);
185 pt = parent!;
186 }
187 }
188 }
189 tree.root!.color = 1; // Root is always black
190}
191
192/**
193 * Finds the node that replaces a deleted node in BST
194 */
195function bstReplace<T>(x: RBTreeNode<T>): RBTreeNode<T> | null {
196 // Node has two children
197 if (x.left && x.right) return successor(x.right);
198 // Node is leaf
199 if (!x.left && !x.right) return null;
200 // Node has single child
201 return x.left ?? x.right;
202}
203
204/**
205 * Finds the leftmost node in subtree (successor)
206 */
207function successor<T>(x: RBTreeNode<T>): RBTreeNode<T> {
208 let temp = x;
209 while (temp.left) temp = temp.left;
210 return temp;
211}
212
213/**
214 * Fixes double black violation after deletion
215 */
216function fixDoubleBlack<T>(tree: RBTree<T>, x: RBTreeNode<T>): void {
217 if (x === tree.root) return; // Reached root
218
219 const sibling = getSibling(x);
220 const parent = x.parent!;
221
222 if (!sibling) {
223 // No sibling - double black pushed up
224 fixDoubleBlack(tree, parent);
225 } else {
226 if (sibling.color === 0) {
227 // Sibling is red
228 parent.color = 0;
229 sibling.color = 1;
230 if (isOnLeft(sibling)) rotateRight(tree, parent);
231 else rotateLeft(tree, parent);
232 fixDoubleBlack(tree, x);
233 } else {
234 // Sibling is black
235 if (hasRedChild(sibling)) {
236 // At least one red child
237 if (sibling.left && sibling.left.color === 0) {
238 if (isOnLeft(sibling)) {
239 // Left-left case
240 sibling.left.color = sibling.color;
241 sibling.color = parent.color;
242 rotateRight(tree, parent);
243 } else {
244 // Right-left case
245 sibling.left.color = parent.color;
246 rotateRight(tree, sibling);
247 rotateLeft(tree, parent);
248 }
249 } else {
250 if (isOnLeft(sibling)) {
251 // Left-right case
252 sibling.right!.color = parent.color;
253 rotateLeft(tree, sibling);
254 rotateRight(tree, parent);
255 } else {
256 // Right-right case
257 sibling.right!.color = sibling.color;
258 sibling.color = parent.color;
259 rotateLeft(tree, parent);
260 }
261 }
262 parent.color = 1;
263 } else {
264 // Two black children
265 sibling.color = 0;
266 if (parent.color === 1) fixDoubleBlack(tree, parent);
267 else parent.color = 1;
268 }
269 }
270 }
271}
272
273/**
274 * Deletes a node from the tree
275 */
276function deleteNode<T>(tree: RBTree<T>, v: RBTreeNode<T>): void {
277 const u = bstReplace(v);
278
279 // Both u and v are black
280 const uvBlack = (u === null || u.color === 1) && v.color === 1;
281 const parent = v.parent!;
282
283 if (!u) {
284 // u is null, v is leaf
285 if (v === tree.root) {
286 tree.root = null;
287 } else {
288 if (uvBlack) {
289 // Both black - fix double black
290 fixDoubleBlack(tree, v);
291 } else {
292 // One is red - make sibling red if exists
293 const sibling = getSibling(v);
294 if (sibling) sibling.color = 0;
295 }
296 // Remove v from tree
297 if (isOnLeft(v)) parent.left = null;
298 else parent.right = null;
299 }
300 return;
301 }
302
303 if (!v.left || !v.right) {
304 // v has one child
305 if (v === tree.root) {
306 // v is root - replace with child
307 v.data = u.data;
308 v.left = v.right = null;
309 } else {
310 // Detach v and move u up
311 if (isOnLeft(v)) parent.left = u;
312 else parent.right = u;
313 u.parent = parent;
314 if (uvBlack) fixDoubleBlack(tree, u);
315 else u.color = 1;
316 }
317 return;
318 }
319
320 // v has two children - swap with successor and recurse
321 swapData(u, v);
322 deleteNode(tree, u);
323}
324
325/**
326 * Inserts a value into the tree
327 */
328function insertTree<T>(tree: RBTree<T>, data: T): boolean {
329 // Search for insertion position
330 let parent = tree.root;
331 while (parent) {
332 if (tree.lt(data, parent.data)) {
333 if (!parent.left) break;
334 else parent = parent.left;
335 } else if (tree.lt(parent.data, data)) {
336 if (!parent.right) break;
337 else parent = parent.right;
338 } else break;
339 }
340
341 // Insert new node
342 const node = createRBTreeNode(data);
343 if (!parent) {
344 tree.root = node;
345 } else if (tree.lt(node.data, parent.data)) {
346 parent.left = node;
347 } else if (tree.lt(parent.data, node.data)) {
348 parent.right = node;
349 } else {
350 // Duplicate value - increment count
351 parent.count++;
352 return false;
353 }
354 node.parent = parent;
355 fixAfterInsert(tree, node);
356 return true;
357}
358
359/**
360 * Finds a node with given data
361 */
362function findNode<T>(tree: RBTree<T>, data: T): RBTreeNode<T> | null {
363 let p = tree.root;
364 while (p) {
365 if (tree.lt(data, p.data)) {
366 p = p.left;
367 } else if (tree.lt(p.data, data)) {
368 p = p.right;
369 } else break;
370 }
371 return p ?? null;
372}
373
374/**
375 * Creates a new TreeSet
376 */
377function createTreeSet<T = number>(
378 collection: T[] | Compare<T> = [],
379 compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0)
380): TreeSet<T> {
381 if (typeof collection === 'function') {
382 compare = collection;
383 collection = [];
384 }
385
386 const treeSet: TreeSet<T> = {
387 size: 0,
388 tree: createRBTree(compare),
389 compare: compare
390 };
391
392 for (const val of collection) {
393 addToTreeSet(treeSet, val);
394 }
395
396 return treeSet;
397}
398
399/**
400 * Adds a value to the TreeSet
401 */
402function addToTreeSet<T>(treeSet: TreeSet<T>, val: T): boolean {
403 const successful = insertTree(treeSet.tree, val);
404 if (successful) treeSet.size++;
405 return successful;
406}
407
408/**
409 * Finds the largest value less than the given value
410 */
411function lower<T>(treeSet: TreeSet<T>, val: T): T | undefined {
412 let p = treeSet.tree.root;
413 let lowerNode = null;
414 while (p) {
415 if (treeSet.compare(p.data, val) < 0) {
416 lowerNode = p;
417 p = p.right;
418 } else {
419 p = p.left;
420 }
421 }
422 return lowerNode?.data;
423}
424
425/**
426 * Finds the maximum triplet value in the array
427 * Returns max(nums[i] - nums[j] + nums[k]) where i < j < k
428 */
429function maximumTripletValue(nums: number[]): number {
430 const n = nums.length;
431
432 // Build array of maximum values to the right of each position
433 const right: number[] = Array(n).fill(nums[n - 1]);
434 for (let i = n - 2; i >= 0; i--) {
435 right[i] = Math.max(nums[i], right[i + 1]);
436 }
437
438 // TreeSet to maintain values to the left of current position
439 const ts = createTreeSet<number>();
440 addToTreeSet(ts, nums[0]);
441
442 let ans = 0;
443
444 // Iterate through middle positions
445 for (let j = 1; j < n - 1; j++) {
446 // Check if there's a larger value to the right
447 if (right[j + 1] > nums[j]) {
448 // Find the largest value less than nums[j] from the left
449 const val = lower(ts, nums[j]);
450 if (val !== undefined) {
451 // Calculate triplet value: nums[i] - nums[j] + nums[k]
452 ans = Math.max(ans, val - nums[j] + right[j + 1]);
453 }
454 }
455 addToTreeSet(ts, nums[j]);
456 }
457
458 return ans;
459}
460
Time and Space Complexity
Time Complexity: O(n × log n)
The algorithm consists of three main parts:
- Building the
right
array: This takesO(n)
time as it iterates through the array once from right to left. - The main loop iterates through indices from 1 to n-2, which is
O(n)
iterations. Within each iteration:sl.bisect_left(nums[j])
performs binary search on the SortedList, takingO(log n)
time in the worst case when the SortedList contains up ton
elements.sl.add(nums[j])
inserts an element into the SortedList while maintaining sorted order, which takesO(log n)
time.- Other operations like comparisons and max calculations take
O(1)
time.
- The dominant operation is the loop with SortedList operations:
O(n) × O(log n) = O(n × log n)
.
Space Complexity: O(n)
The algorithm uses:
- The
right
array which storesn
elements:O(n)
space. - The SortedList
sl
which can contain up ton-1
elements in the worst case:O(n)
space. - A few variables for indices and the answer:
O(1)
space.
The total space complexity is O(n) + O(n) + O(1) = O(n)
.
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Forgetting to Check Valid Triplet Existence Before Calculation
The Pitfall: A common mistake is attempting to calculate the triplet value without first verifying that a valid increasing triplet exists. This can happen when:
- There's no element to the left that's smaller than
nums[j]
- There's no element to the right that's larger than
nums[j]
Example of Incorrect Code:
# WRONG: Assumes valid elements always exist
for j in range(1, n - 1):
left_index = sorted_left.bisect_left(nums[j]) - 1
# Dangerous: directly using left_index without checking if >= 0
triplet_value = sorted_left[left_index] - nums[j] + right_max[j + 1]
max_triplet_value = max(max_triplet_value, triplet_value)
Why It Fails:
- If
nums[j]
is the smallest element seen so far,bisect_left(nums[j]) - 1
returns-1
- Accessing
sorted_left[-1]
gives the last element (largest), not what we want - This violates the increasing order constraint
nums[i] < nums[j]
The Solution: Always validate both conditions before calculating:
for j in range(1, n - 1):
# First check: Is there a valid k? (element > nums[j] on the right)
if right_max[j + 1] > nums[j]:
left_index = sorted_left.bisect_left(nums[j]) - 1
# Second check: Is there a valid i? (element < nums[j] on the left)
if left_index >= 0:
triplet_value = sorted_left[left_index] - nums[j] + right_max[j + 1]
max_triplet_value = max(max_triplet_value, triplet_value)
2. Incorrect Handling of Duplicate Values
The Pitfall:
When the array contains duplicate values, using bisect_right
instead of bisect_left
can lead to incorrect results.
Example Scenario:
nums = [3, 5, 5, 7] # At j=2 (nums[j]=5), sorted_left = [3, 5] # Using bisect_right(5) returns 2, so index 2-1=1 gives sorted_left[1]=5 # This violates nums[i] < nums[j] since 5 is not less than 5
The Solution:
Use bisect_left
to ensure we get elements strictly less than nums[j]
:
# Correct: bisect_left ensures we find elements strictly less than nums[j] left_index = sorted_left.bisect_left(nums[j]) - 1
3. Off-by-One Errors in Suffix Array Construction
The Pitfall: Building the suffix maximum array incorrectly, especially with the loop boundaries.
Example of Incorrect Code:
# WRONG: Missing the last element or incorrect initialization
right_max = [0] * n # Wrong initialization
for i in range(n - 1, 0, -1): # Wrong range - skips index 0
right_max[i] = max(nums[i], right_max[i + 1])
The Solution: Properly initialize and iterate through all indices:
# Correct: Initialize with last element and iterate backwards including index 0
right_max = [nums[-1]] * n
for i in range(n - 2, -1, -1):
right_max[i] = max(nums[i], right_max[i + 1])
4. Adding Elements to SortedList at Wrong Time
The Pitfall:
Adding nums[j]
to the sorted list before processing it as the middle element can cause incorrect results.
Example of Incorrect Code:
for j in range(1, n - 1):
sorted_left.add(nums[j]) # WRONG: Added too early
# Now sorted_left contains nums[j], which shouldn't be considered for i
left_index = sorted_left.bisect_left(nums[j]) - 1
# This might select nums[j] itself as nums[i]
The Solution:
Add nums[j]
to the sorted list only after processing it:
for j in range(1, n - 1):
# Process nums[j] as middle element first
if right_max[j + 1] > nums[j]:
left_index = sorted_left.bisect_left(nums[j]) - 1
if left_index >= 0:
# Calculate triplet value
...
# Add nums[j] AFTER processing
sorted_left.add(nums[j])
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!