Facebook Pixel

3073. Maximum Increasing Triplet Value 🔒

MediumArrayOrdered Set
Leetcode Link

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 be 5 - 6 + 9 = 8.
  • In the array [1,5,3,6], there are two valid triplets:
    • Indices (0, 1, 3) with values (1, 5, 6) giving 1 - 5 + 6 = 2
    • Indices (0, 2, 3) with values (1, 3, 6) giving 1 - 3 + 6 = 4
    • The maximum is 4

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]).

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

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 of j where nums[i] < nums[j]
  • We need to find the largest nums[k] to the right of j where nums[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:

  1. By iterating through all possible middle elements j, we ensure we don't miss the optimal triplet
  2. For each j, we're finding the best possible i and k that satisfy our constraints
  3. The sorted structure (like SortedList in Python) allows us to efficiently find the best nums[i] in O(log n) time
  4. 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 where nums[j] would be inserted
  • Subtracting 1 gives us the index of the largest element less than nums[j]
  • If i >= 0, then sl[i] is our optimal nums[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 Evaluator

Example 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]: Is 8 > 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]: Is 8 > 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]: Is 8 > 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]: Is 3 > 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:

  1. Building the right array: This takes O(n) time as it iterates through the array once from right to left.
  2. 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, taking O(log n) time in the worst case when the SortedList contains up to n elements.
    • sl.add(nums[j]) inserts an element into the SortedList while maintaining sorted order, which takes O(log n) time.
    • Other operations like comparisons and max calculations take O(1) time.
  3. 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:

  1. The right array which stores n elements: O(n) space.
  2. The SortedList sl which can contain up to n-1 elements in the worst case: O(n) space.
  3. 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])
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Recommended Readings

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

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 Review

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 to Algo Cheat Sheet

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!

Load More