3073. Maximum Increasing Triplet Value

MediumArrayOrdered Set
Leetcode Link

Problem Description

The task is to find the maximum value from a triplet in an array of integers. A triplet (i, j, k) is defined by three conditions:

  1. The indices i, j, and k follow an increasing sequence (i < j < k).
  2. The values at those indices in the array also follow an increasing sequence (nums[i] < nums[j] < nums[k]).
  3. The value of the triplet is calculated using the formula nums[i] - nums[j] + nums[k].

One needs to return the highest possible value from any triplet in the array that satisfies the conditions above.

Intuition

To find the maximum value of a triplet (i, j, k), we need to consider two main aspects:

  1. Maximizing nums[i] with the condition nums[i] < nums[j].
  2. Maximizing nums[k] with the condition nums[k] > nums[j].

To get the largest possible value for the triplet, we aim to pick the largest nums[i] that is less than nums[j] and the largest nums[k] that is greater than nums[j]. Since nums[j] is the constant middle value in our triplet calculation (nums[i] - nums[j] + nums[k]), we can traverse the array and keep track of possible nums[i] and nums[k] for each j.

To approach the solution, we'll implement two main strategies:

  1. We prepare a suffix array right such that right[i] holds the maximum value to the right of i, including i. This helps us quickly fetch the maximum k value for any given j.

  2. We use an ordered set to keep track of all the values to the left of j encountered so far. This set will help us efficiently query for the largest value less than nums[j] which serves as a candidate for nums[i].

The solution is a blend of dynamic programming (with the use of the right array) and binary search (using the ordered set to quickly find the largest element smaller than nums[j]). We loop through the array only once and, at each step, take logarithmic time to update our ordered set and find the needed value, leading to an efficient algorithm for the problem.

Solution Approach

In the given solution, we make use of three primary components:

  1. A suffix array named right
  2. An ordered set from the sortedcontainers library
  3. A single pass loop to consider each nums[j]

Suffix Array right

The right array is a dynamic programming technique. We start from the end of the array and move towards the start, filling right[i] with the maximum value encountered from index i to the end of the array. This ensures that for any index j, right[j+1] will provide the maximum value available for nums[k] where k > j.

Here is the implementation:

1right = [nums[-1]] * n
2for i in range(n - 2, -1, -1):
3    right[i] = max(nums[i], right[i + 1])

We initialize the right array to be of the same length as nums, filled with the last element of nums. We then traverse the array from the second-to-last element to the first, updating each right[i] to be the maximum of nums[i] and right[i+1].

Ordered Set

The ordered set from the sortedcontainers library acts similar to a balanced binary search tree. It maintains the sorted order of elements and provides efficient operations to add elements and to search for an element by its order.

Here's how it's used:

1sl = SortedList([nums[0]])
2for j in range(1, n - 1):
3    if right[j + 1] > nums[j]:
4        i = sl.bisect_left(nums[j]) - 1
5        if i >= 0:
6            ans = max(ans, sl[i] - nums[j] + right[j + 1])
7    sl.add(nums[j])

We initialize our ordered set sl with the first element of nums and start our one pass through the array, considering each j from 1 to n - 2. For each j, we check if there's a valid k by confirming that right[j + 1] (the largest nums[k] after j) is greater than nums[j]. If so, we use sl.bisect_left(nums[j]) which gives us an index one greater than the index of the largest number less than nums[j] in sl. We then decrease it by 1 to get the correct index for nums[i]. If such an index exists (i >= 0), we calculate the value of the current triplet and update our answer ans if it's greater than the previous maximum.

The ordered set guarantees logarithmic time complexity for both the addition and the bisect_left operation.

With the combination of the suffix array right and the ordered set sl, we're able to find the maximum triplet value efficiently as we only make one pass through the array and maintain a set of potential i values for each j, from which we can quickly determine the maximum possible value of nums[i].

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Example Walkthrough

Let's assume our given array of integers is nums = [3, 5, 1, 6, 4]. We want to find the maximum value of a triplet (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k] using the value calculated by nums[i] - nums[j] + nums[k].

We initialize our three primary components:

  1. The suffix array right is created to store the maximum values to the right of each index, including the index itself.
  2. An ordered set sl from the sortedcontainers library.
  3. An answer variable ans initialized to minus infinity to store the maximum value of the triplets found.

Let's walk through the implementation step by step with our array nums = [3, 5, 1, 6, 4]:

Step 1: Create the Suffix Array

We start by populating our right array with the maximum value to the right of each index in nums.

1right = [4, 4, 6, 6, 4]  # Initialized with the max to the right of each index

The right array would be filled as follows:

  • Start from nums[4] = 4, so right[4] is 4.
  • Check max(nums[3], right[4]), which is max(6, 4) = 6, so right[3] is 6.
  • Following the pattern, right[2] is 6, right[1] is 6, and right[0] is 6.

We fill right from nums[-1] to nums[0] by taking the maximum of the current element and the next element in right.

Step 2: Initialize the Ordered Set and Iterate

Next, we initialize our ordered set sl with the first element of nums.

1sl = SortedList([3])
2ans = float('-inf')  # This represents negative infinity to start with no valid max.

Step 3: Iterate through nums

Now, we iterate from 1 to len(nums) - 2 because these are the potential j positions for a valid triplet.

For j = 1, nums[j] = 5.

  • We check right[j + 1] which is 6, and since 6 > 5, we proceed.
  • Find the largest value less than 5 in sl using sl.bisect_left(5) - 1 which gives 0.
  • The element at 0 in sl is 3, so we calculate the triplet value 3 - 5 + 6 = 4.
  • Since ans is -inf, we update ans with 4.
  • Add nums[j] to sl.

Continue this process for j = 2, 3, and by the end of this single pass, we have considered all valid triplets.

Assuming we update ans appropriately through each iteration, at the end of this process, ans would hold the maximum triplet value. With the nums array given, the maximum triplet value we compute would be 1 - 5 + 6 = 2.

With this efficient approach utilizing the right array for the maximum k value and the ordered set for the maximum i value corresponding to each j, we can determine the highest possible value from any triplet following the conditions.

This walk-through demonstrates the solution approach on a small example and how it translates into finding the desired maximum value of the triplet in an array of integers.

Solution Implementation

1from sortedcontainers import SortedList
2from typing import List
3
4class Solution:
5    def maximum_triplet_sum(self, nums: List[int]) -> int:
6        n = len(nums)  # Get the length of the nums array
7        max_from_right = [nums[-1]] * n  # Create a list to store maximum values from the right
8      
9        # Fill the max_from_right list with the max value seen from the right for each position
10        for i in range(n - 2, -1, -1):
11            max_from_right[i] = max(nums[i], max_from_right[i + 1])
12          
13        # Initialize a SortedList with the first element of nums
14        sorted_left = SortedList([nums[0]])
15        answer = 0  # Variable to store the maximum triplet sum
16      
17        # Iterate through the numbers, ignoring the first and last elements
18        for j in range(1, n - 1):
19            # Check if a larger number exists to the right of the current position
20            if max_from_right[j + 1] > nums[j]:
21                # Find the first number in the sorted list that is greater than or equal to nums[j]
22                i = sorted_left.bisect_left(nums[j]) - 1
23                # If there's a number on the left smaller than nums[j], calculate a new triplet sum
24                if i >= 0:
25                    triplet_sum = sorted_left[i] + nums[j] + max_from_right[j + 1]
26                    answer = max(answer, triplet_sum)  # Update the maximum triplet sum if necessary
27            # Add the current number to the sorted list for future iterations
28            sorted_left.add(nums[j])
29          
30        return answer  # Return the maximum triplet sum found
31
1class Solution {
2    public int maximumTripletValue(int[] nums) {
3        // Get the length of the input array 'nums'
4        int n = nums.length;
5
6        // Initialize the 'rightMax' array to store the maximum value to the right of each element
7        int[] rightMax = new int[n];
8        // The maximum value of the rightmost element is the element itself
9        rightMax[n - 1] = nums[n - 1];
10
11        // Precompute the maximum values to the right of each element in the array
12        for (int i = n - 2; i >= 0; i--) {
13            rightMax[i] = Math.max(nums[i], rightMax[i + 1]);
14        }
15
16        // Use TreeSet to efficiently find values
17        TreeSet<Integer> leftValues = new TreeSet<>();
18        // Add the first element to the TreeSet
19        leftValues.add(nums[0]);
20
21        // Initialize 'maxTripletValue' to store the maximum value of the triplet sum
22        int maxTripletValue = 0;
23
24        // Iterate over the elements of the array, starting from the second element and
25        // ending at the second to last element
26        for (int j = 1; j < n - 1; ++j) {
27            // Only process if the maximum to the right is greater than the current element
28            if (rightMax[j + 1] > nums[j]) {
29                // Fetch the highest value in the TreeSet that is lower than the current element
30                Integer leftMax = leftValues.lower(nums[j]);
31                if (leftMax != null) {
32                    // Calculate the current triplet value and update the maximum if necessary
33                    maxTripletValue = Math.max(maxTripletValue, leftMax - nums[j] + rightMax[j + 1]);
34                }
35            }
36            // Add the current element to the TreeSet for future iterations
37            leftValues.add(nums[j]);
38        }
39        // Return the maximum triplet value found
40        return maxTripletValue;
41    }
42}
43
1#include <vector>
2#include <set>
3#include <algorithm>
4
5class Solution {
6public:
7    // Function to calculate the maximum triplet value in the array.
8    // The triplet value of position j is defined as nums[i] + nums[j] + nums[k],
9    // where i < j < k and nums[i] < nums[j] < nums[k].
10    int maximumTripletValue(vector<int>& nums) {
11        int n = nums.size(); // Store the size of 'nums'.
12        vector<int> maxRight(n, nums.back()); // Create a vector to store the max value to the right of each position.
13      
14        // Populate 'maxRight' with the maximum value found to the right of each index.
15        for (int i = n - 2; i >= 0; --i) {
16            maxRight[i] = max(nums[i], maxRight[i + 1]);
17        }
18      
19        set<int> leftSet; // Using a set to keep track of the elements visited on the left.
20        leftSet.insert(nums[0]); // Insert the first element.
21      
22        int maxTripletSum = 0; // Initialize the maximum triplet value.
23      
24        // Iterate through the array starting from the second element until the second to last.
25        for (int j = 1; j < n - 1; ++j) {
26            // Check if there is an element greater than nums[j] to the right.
27            if (maxRight[j + 1] > nums[j]) {
28                // Find the greatest element less than nums[j] using lower_bound which points to the first element not less.
29                auto it = leftSet.lower_bound(nums[j]);
30                if (it != leftSet.begin()) { // Ensure that the iterator is not at the beginning.
31                    --it; // Move the iterator to the largest element that is less than nums[j].
32                    // Calculate the triplet value and update the maximum triplet sum.
33                    maxTripletSum = max(maxTripletSum, *it + nums[j] + maxRight[j + 1]);
34                }
35            }
36            // Insert the current element into the set for left-side tracking.
37            leftSet.insert(nums[j]);
38        }
39      
40        // Return the maximum triplet sum found.
41        return maxTripletSum;
42    }
43};
44
1// Declaration of the comparison function type
2type Comparator<T> = (lhs: T, rhs: T) => number;
3
4// Declaration of the Red-Black Tree Node
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 for Red, 1 for Black
12}
13
14// Utility function to create a new Red-Black Tree Node
15function createRBTreeNode<T>(data: T): RBTreeNode<T> {
16  return {
17    data: data,
18    count: 1,
19    left: null,
20    right: null,
21    parent: null,
22    color: 0
23  };
24}
25
26// Red-Black Tree Node methods
27function isOnLeft<T>(node: RBTreeNode<T>): boolean {
28  return node === node.parent!.left;
29}
30
31function sibling<T>(node: RBTreeNode<T>): RBTreeNode<T> | null {
32  if (!node.parent) return null;
33  return isOnLeft(node) ? node.parent.right : node.parent.left;
34}
35
36function hasRedChild<T>(node: RBTreeNode<T>): boolean {
37  return Boolean(node.left && node.left.color === 0) || Boolean(node.right && node.right.color === 0);
38}
39
40// Define global variables for the Red-Black Tree
41let rbTreeRoot: RBTreeNode | null = null;
42let rbTreeLt: Comparator<any>;
43
44// Define functions to manipulate the Red-Black Tree
45function rotateLeft<T>(pt: RBTreeNode<T>): void {
46  // Function logic here
47}
48// Other rotation, color swapping, and fix-up functions omitted for brevity
49
50// Define functions for TreeSet operations
51function maximumTripletValue(nums: number[]): number {
52  // Function logic here
53}
54// Other TreeSet methods omitted for brevity
55
56// Usage of TreeSet functions
57const myNumbers: number[] = [3, 1, 4, 1, 5, 9, 2, 6, 5];
58const maxTripletVal: number = maximumTripletValue(myNumbers);
59console.log(`Maximum Triplet Value: ${maxTripletVal}`);
60
61// Note: The refactoring above is not complete as the full code has been omitted for brevity.
62// All the methods and properties of the Red-Black Tree and TreeSet should be refactored similarly.
63

Time and Space Complexity

The time complexity of the given code can be analyzed by looking at each segment of the code:

  1. Building the right array: The array is created by iterating over the nums array from right to left once, which has a complexity of O(n).

  2. The main for-loop runs from j = 1 to n - 1: Within the loop, the following operations occur:

    • Checking if right[j + 1] > nums[j]: This is an O(1) operation.
    • Executing sl.bisect_left(nums[j]): The SortedList uses a binary search technique to find the leftmost insertion point which takes O(log n) time.
    • Conditionally updating ans based on the i index: This is an O(1) operation.
    • Finally, sl.add(nums[j]): Adding an element to the SortedList which maintains a sorted order takes O(log n) time.

Considering the loop runs (n - 2) times and the most expensive operations inside are O(log n), the complexity of the loop becomes O(n * log n).

Combining the complexity of building the right array and the main loop, the overall time complexity remains O(n * log n) as the loop's complexity dominates.

The space complexity analysis includes:

  1. The right array: As it stores n elements, it has a complexity of O(n).

  2. The SortedList sl: In the worst case, this will hold n elements, resulting in a space complexity of O(n).

Hence, the overall space complexity is also O(n) since these two data structures are the dominant factors in space usage, and their complexities are additive.

In conclusion, the code exhibits a time complexity of O(n * log n) and a space complexity of O(n).

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What are the most two important steps in writing a depth first search function? (Select 2)


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄