2921. Maximum Profitable Triplets With Increasing Prices II

HardBinary Indexed TreeSegment TreeArray
Leetcode Link

Problem Description

The problem presents us with two arrays, prices and profits, each of length n. These arrays represent items in a store, where prices[i] indicates the price of the i-th item and profits[i] represents the profit that can be earned from selling the i-th item. Our goal is to select three items indexed as i, j, and k (with the conditions that i < j < k and prices[i] < prices[j] < prices[k]) to maximize our total profit, which would be the sum of the individual profits from the three items (profits[i] + profits[j] + profits[k]). If there is no possible way to choose three such items, we must return -1.

Intuition

To find the maximum profit with the given constraints, we could consider using a brute-force solution where we would check every possible combination of three items to find the maximum profit. However, with n items, this approach would result in a time complexity of O(n^3), which is inefficient and impractical for large inputs.

Instead, we use a more optimized approach with Binary Indexed Trees (BITs), also known as Fenwick trees. BITs are data structures that allow us to efficiently compute prefix sums and/or maximums for a sequence of numbers and perform updates in logarithmic time. We can use them to keep track of the highest profit we can get up to a certain price when examining prices from left to right (for the i-th item) and from right to left (for the k-th item).

The intuition behind the solution is as follows:

  1. We traverse the prices array from left to right and for each i-th item, we use the first BIT to find the maximum profit we could achieve from items with a lower price (this represents the possible profit from the j-th item if we were to choose the i-th item).
  2. Similarly, we traverse the prices array from right to left and for each i-th item, we use the second BIT to find the maximum profit from items with a higher price.
  3. As we process each item, we update our BIT with the new profit if it is higher than the current profit stored at that price point.
  4. Finally, we iterate over the items again and, using both BITs, we calculate the total potential profit for each item if it were chosen as the middle item (j-th). We keep track of the maximum of these sums.

As the profit is only valid if we have a lower-priced item with a profit and a higher-priced item with a profit, we ensure that the "left" and "right" profits are non-zero before considering the total profit. By using BITs, we obtain an efficient solution with a time complexity of O(n log m), where m is the maximum price among the items.

Learn more about Segment Tree patterns.

Solution Approach

The solution makes use of two Binary Indexed Trees (BITs) to effectively find the maximum profits that can be obtained to the left and to the right of a particular price[i]. The implementation follows four main steps:

  1. Initialization of the Binary Indexed Trees - The BinaryIndexedTree class is used to create two BITs, tree1 and tree2. These will respectively keep track of the maximum profit we can have to the left of each price (tree1) and to the right of each price (tree2).

  2. Pre-calculation of the maximum profits to the left - As we iterate over the prices array from left to right, we use the tree1 BIT to find the greatest profit that can be achieved from items with a smaller price than the current price. This value is stored in an array called left[]. Simultaneously, we also update tree1 with the current profit if it exceeds the currently stored maximum profit at that price point.

  3. Pre-calculation of the maximum profits to the right - Similarly, we iterate through the prices array from right to left using the BIT tree2 this time. We store the maximum possible profit to the right of the current price (for higher priced items) in an array called right[]. Additionally, updates are made to tree2 with the current profit as in the previous step but indexed in a different manner to account for the directional difference in the traversal.

  4. Finding the maximum total profit - After populating left[] and right[] with the respective pre-calculated profits, we make a final pass through the arrays. In this pass, we add the profits[i] to left[i] and right[i] for each i, where both left[i] and right[i] are non-zero. This condition ensures that we only consider valid sequences where prices[i] is less than prices[j] and less than prices[k]. The maximum sum obtained from this step represents our answer, with -1 returned as a default if no such sequence exists.

One key aspect to understand is that during the iteration, the profits are only updated in the BITs if the new potential profit for a given price is higher than the current stored profit. This ensures that the BITs always reflect the maximum potential profit for any price up to the current iterating price. By utilizing these optimized data structures and algorithmic steps, we are able to efficiently calculate the maximum profit that satisfies the given conditions without having to resort to overly time-consuming brute-force methods.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach:

Suppose we have the following arrays:

  • prices = [3, 4, 5, 1, 6]
  • profits = [1, 2, 3, 4, 5]

According to our problem, we want to select three items such that i < j < k and prices[i] < prices[j] < prices[k] to maximize our profit profits[i] + profits[j] + profits[k].

Step 1: Initializing the BITs

We initialize two Binary Indexed Trees (BITs), tree1 and tree2, which will help us keep track of the maximum profit to the left and right of each price point.

Step 2: Pre-calculate maximum profits to the left

As we traverse the prices array from left to right:

  • At prices[0] = 3, the left maximum profit cannot be calculated because there are no previous items. So, left[0] remains 0.
  • At prices[1] = 4, the left maximum profit is 1 (the profit of the previous lower priced item), so we update left[1] = 1.
  • At prices[2] = 5, the left maximum profit is 2 (the profit of the previous lower priced item at prices[1]), so left[2] = 2.
  • At prices[3] = 1, this item's price is lower than all previous items, so left[3] remains 0.
  • At prices[4] = 6, the left maximum profit is 3 (previous lower priced item's profit at prices[2]), so left[4] = 3.

Also, we update tree1 respectively with profits if they are higher than the current profit at that price point.

Step 3: Pre-calculate maximum profits to the right

We traverse the prices array from right to left:

  • At prices[4] = 6, the right maximum profit cannot be calculated because there are no following items. So, right[4] remains 0.
  • At prices[3] = 1, since no higher priced items have been encountered yet, right[3] remains 0.
  • At prices[2] = 5, the right maximum profit is 5 (the profit of next higher priced item at prices[4]), so right[2] = 5.
  • At prices[1] = 4, the right maximum profit is 5, so right[1] = 5.
  • At prices[0] = 3, the right maximum profit is 5, so right[0] = 5.

tree2 is updated in the same way as tree1, but in the reverse order.

Step 4: Finding the maximum total profit

We now consider each item as a potential middle item for a valid sequence:

  • For prices[0] = 3, we have left[0] = 0 and right[0] = 5. Since left[0] is zero, we ignore this.
  • For prices[1] = 4, we have left[1] = 1 and right[1] = 5. The total profit is 1 + 2 + 5 = 8.
  • For prices[2] = 5, we have left[2] = 2 and right[2] = 5. The total profit is 2 + 3 + 5 = 10.
  • For prices[3] = 1, left[3] and right[3] are both zero, so we ignore this.
  • For prices[4] = 6, left[4] = 3 and right[4] = 0. Since right[4] is zero, we ignore this.

The highest total profit from the sequence that satisfies all conditions is 10 for the combination of items with prices 4, 5, and 6 and profits 2, 3, and 5 respectively.

Therefore, we would return 10 as the maximum profit that can be made under the given constraints. If we did not find any valid sequence of items, we would return -1.

Solution Implementation

1from typing import List
2
3class BinaryIndexedTree:
4  
5    def __init__(self, size: int):
6        # The size of the tree is determined by the input.
7        self.size = size
8        # Initialize the binary indexed tree with 0 values.
9        self.tree = [0] * (size + 1)
10
11    def update(self, index: int, value: int):
12        # Update the tree by setting the maximum at the index 
13        # and all the relevant indexes upwards.
14        while index <= self.size:
15            self.tree[index] = max(self.tree[index], value)
16            index += index & -index  # Move to the next index to be updated.
17
18    def query(self, index: int) -> int:
19        # Query the tree for the maximum value until the given index.
20        maximum = 0
21        while index:
22            maximum = max(maximum, self.tree[index])
23            index -= index & -index  # Move to the next index for querying the max.
24        return maximum
25
26
27class Solution:
28  
29    def max_profit(self, prices: List[int], profits: List[int]) -> int:
30        # Calculate the maximum profit that can be achieved with given prices and individual profits.
31        num_items = len(prices)
32        max_left_profit = [0] * num_items
33        max_right_profit = [0] * num_items
34
35        # Find the maximum price as the size for the BITs.
36        max_price = max(prices)
37
38        # Initialize two binary indexed trees.
39        tree_before = BinaryIndexedTree(max_price + 1)
40        tree_after = BinaryIndexedTree(max_price + 1)
41
42        # Calculate the maximum profit to the left and right for each item.
43        for i, price in enumerate(prices):
44            max_left_profit[i] = tree_before.query(price - 1)
45            tree_before.update(price, profits[i])
46
47        # The loop goes backwards to calculate the right profits.
48        for i in range(num_items - 1, -1, -1):
49            price = max_price + 1 - prices[i]
50            max_right_profit[i] = tree_after.query(price - 1)
51            tree_after.update(price, profits[i])
52
53        # Calculate the overall maximum profit by considering the left and right profits
54        # and the current profit for each item.
55        return max(
56            (left + profit + right for left, profit, right in zip(max_left_profit, profits, max_right_profit) if left and right),
57            default=-1
58        )
59
1class BinaryIndexedTree {
2    private int size;
3    private int[] tree;
4
5    // Construct a Binary Indexed Tree with given size
6    public BinaryIndexedTree(int size) {
7        this.size = size;
8        tree = new int[size + 1];
9    }
10
11    // Update the Binary Indexed Tree at index `index` with value `value`
12    // using point update operation where each node stores the maximum value
13    public void update(int index, int value) {
14        while (index <= size) {
15            tree[index] = Math.max(tree[index], value);
16            index += index & -index;
17        }
18    }
19
20    // Query the maximum value in the range [1, index]
21    public int query(int index) {
22        int max = 0;
23        while (index > 0) {
24            max = Math.max(max, tree[index]);
25            index -= index & -index;
26        }
27        return max;
28    }
29}
30
31class Solution {
32    // Calculate the maximum profit that can be obtained by buying and selling the 
33    // items given the prices and profits of each item
34    public int maxProfit(int[] prices, int[] profits) {
35        int n = prices.length;
36        int maxPrice = 0;
37      
38        // Track the prefix maximum profit from left and right
39        int[] prefixMaxLeft = new int[n];
40        int[] prefixMaxRight = new int[n];
41      
42        // Find out the maximum price for item initialization
43        for (int price : prices) {
44            maxPrice = Math.max(maxPrice, price);
45        }
46      
47        // Initialize two Binary Indexed Trees
48        BinaryIndexedTree treeFromLeft = new BinaryIndexedTree(maxPrice + 1);
49        BinaryIndexedTree treeFromRight = new BinaryIndexedTree(maxPrice + 1);
50      
51        // Scan from left to right and update prefixMaxLeft with the maximum profit seen so far
52        for (int i = 0; i < n; ++i) {
53            int price = prices[i];
54            prefixMaxLeft[i] = treeFromLeft.query(price - 1);
55            treeFromLeft.update(price, profits[i]);
56        }
57      
58        // Scan from right to left and update prefixMaxRight with the maximum profit seen so far
59        for (int i = n - 1; i >= 0; --i) {
60            // Invert price to keep the non-decreasing order when scanning from right to left
61            int invertedPrice = maxPrice + 1 - prices[i];
62            prefixMaxRight[i] = treeFromRight.query(invertedPrice - 1);
63            treeFromRight.update(invertedPrice, profits[i]);
64        }
65      
66        // Calculate the maximum profit by taking the max of the profit obtainable at each index
67        int maxProfit = -1; // Initialize it to -1 to represent no valid transaction performed
68        for (int i = 0; i < n; ++i) {
69            if (prefixMaxLeft[i] > 0 && prefixMaxRight[i] > 0) {
70                maxProfit = Math.max(maxProfit, prefixMaxLeft[i] + profits[i] + prefixMaxRight[i]);
71            }
72        }
73      
74        return maxProfit;
75    }
76}
77
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5// Class for the Binary Indexed Tree (BIT), also known as Fenwick Tree.
6class BinaryIndexedTree {
7private:
8    int size;              // The size of the original array
9    vector<int> tree;      // The array representation of the binary indexed tree
10
11public:
12    // Constructor initializes the BIT with the given size.
13    explicit BinaryIndexedTree(int size) {
14        this->size = size;
15        tree.resize(size + 1, 0);
16    }
17
18    // Updates the BIT with a value 'v' at index 'index'.
19    void update(int index, int value) {
20        while (index <= size) {
21            tree[index] = max(tree[index], value); // Store the maximum value up to the current index
22            index += index & -index;              // Move to the parent node in the update viewpoint
23        }
24    }
25
26    // Queries the maximum value in the BIT up to index 'index'.
27    int query(int index) {
28        int maxVal = 0;
29        while (index > 0) {
30            maxVal = max(maxVal, tree[index]);   // Obtain the maximum value from the tree
31            index -= index & -index;             // Move to the parent node in the query viewpoint
32        }
33        return maxVal;
34    }
35};
36
37// The Solution class contains the method to determine the maximum profit.
38class Solution {
39public:
40    // Calculates the maximum profit for buying and selling stocks.
41    int maxProfit(vector<int>& prices, vector<int>& profits) {
42        int itemCount = prices.size();                             // The number of items
43        vector<int> leftMaxProfit(itemCount, 0);                  // Max profit to the left of an index
44        vector<int> rightMaxProfit(itemCount, 0);                 // Max profit to the right of an index
45        int maxPrice = *max_element(prices.begin(), prices.end()); // Maximum price to determine BIT size
46      
47        BinaryIndexedTree treeBefore(maxPrice + 1);
48        BinaryIndexedTree treeAfter(maxPrice + 1);
49      
50        // Calculate the maximum profit before each index
51        for (int i = 0; i < itemCount; ++i) {
52            int currentPrice = prices[i];
53            leftMaxProfit[i] = treeBefore.query(currentPrice - 1);
54            treeBefore.update(currentPrice, profits[i]);
55        }
56      
57        // Calculate the maximum profit after each index
58        for (int i = itemCount - 1; i >= 0; --i) {
59            int adjustedPrice = maxPrice + 1 - prices[i];
60            rightMaxProfit[i] = treeAfter.query(adjustedPrice - 1);
61            treeAfter.update(adjustedPrice, profits[i]);
62        }
63      
64        // Find the maximum profit that can be achieved by buying and selling a stock
65        int maxTotalProfit = -1; // Initialize with -1 to represent no transaction
66        for (int i = 0; i < itemCount; ++i) {
67            if (leftMaxProfit[i] > 0 && rightMaxProfit[i] > 0) { // Check if a profit can be made at current index
68                maxTotalProfit = max(maxTotalProfit, leftMaxProfit[i] + profits[i] + rightMaxProfit[i]);
69            }
70        }
71        return maxTotalProfit;  // Return the maximum profit found
72    }
73};
74
1// Constants representing the size of the binary indexed tree (BIT)
2let treeSize: number;
3let treeArray: number[];
4
5// Initialize the data structure for BIT with a specified size
6function init(n: number): void {
7    treeSize = n;
8    treeArray = Array(n + 1).fill(0);
9}
10
11// Update the BIT with a value at a specific index
12function update(index: number, value: number): void {
13    while (index <= treeSize) {
14        // We use the max operation for this update as per the problem's requirements
15        treeArray[index] = Math.max(treeArray[index], value);
16        // Move to the next index to be updated
17        index += index & -index;
18    }
19}
20
21// Query the BIT to find the maximum value up to a certain index
22function query(index: number): number {
23    let maxVal = 0;
24    while (index > 0) {
25        maxVal = Math.max(maxVal, treeArray[index]);
26        // Move to the next index to continue the query
27        index -= index & -index;
28    }
29    return maxVal;
30}
31
32// Function to calculate the max profit from price and profit arrays
33function maxProfit(prices: number[], profits: number[]): number {
34    const n = prices.length;
35    const maxPrice = Math.max(...prices); // Get the maximum price for the BIT size
36
37    init(maxPrice + 1); // Initialize the BIT with the size of the maximum price + 1
38
39    let leftMaxes = Array(n).fill(0); // Array to store the max profit up to the current price from the left
40    let rightMaxes = Array(n).fill(0); // Array to store the max profit up to the current price from the right
41
42    // Build the BIT from the left for each price and keep track of maximum profit at each point
43    for (let i = 0; i < n; i++) {
44        const currentPrice = prices[i];
45        leftMaxes[i] = query(currentPrice - 1); // Current max profit before this price
46        update(currentPrice, profits[i]); // Update the BIT with the current profit
47    }
48
49    init(maxPrice + 1); // Reinitialize the BIT for right side calculations
50
51    // Build the BIT from the right for each price and keep track of maximum profit at each point
52    for (let i = n - 1; i >= 0; i--) {
53        const currentPrice = maxPrice + 1 - prices[i];
54        rightMaxes[i] = query(currentPrice - 1); // Current max profit before this price from the right
55        update(currentPrice, profits[i]); // Update the BIT with the current profit
56    }
57
58    let maxProfit = -1; // Initialize maxProfit with -1 assuming no transaction is done
59
60    // For each price point, calculate the maximum profit if purchased and sold at that price
61    for (let i = 0; i < n; i++) {
62        if (leftMaxes[i] > 0 && rightMaxes[i] > 0) {
63            maxProfit = Math.max(maxProfit, leftMaxes[i] + profits[i] + rightMaxes[i]);
64        }
65    }
66
67    return maxProfit; // Return the maximum achievable profit
68}
69

Time and Space Complexity

The time complexity of the given code is O(n * log M) where n is the number of elements in the prices array and M is the maximum value in the prices array. This complexity arises because for each price, we perform an update and query operation on the BinaryIndexedTree, both of which have a time complexity of O(log M). Since these operations are performed for each element in the array, the total time complexity becomes O(n * log M).

The space complexity of the code is O(M). This is due to the size of the BinaryIndexedTree used for both tree1 and tree2. Each tree has an internal array c whose size depends on the maximum value in prices, which is M, resulting in a space complexity linear with respect to M.

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


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which data structure is used to implement priority queue?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!


Load More