2921. Maximum Profitable Triplets With Increasing Prices II
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:
- 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).
- 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.
- 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.
- 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.
Which of the following array represent a max heap?
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:
-
Initialization of the Binary Indexed Trees - The
BinaryIndexedTreeclass is used to create two BITs,tree1andtree2. 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). -
Pre-calculation of the maximum profits to the left - As we iterate over the
pricesarray from left to right, we use thetree1BIT 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 calledleft[]. Simultaneously, we also updatetree1with the current profit if it exceeds the currently stored maximum profit at that price point. -
Pre-calculation of the maximum profits to the right - Similarly, we iterate through the
pricesarray from right to left using the BITtree2this time. We store the maximum possible profit to the right of the current price (for higher priced items) in an array calledright[]. Additionally, updates are made totree2with the current profit as in the previous step but indexed in a different manner to account for the directional difference in the traversal. -
Finding the maximum total profit - After populating
left[]andright[]with the respective pre-calculated profits, we make a final pass through the arrays. In this pass, we add theprofits[i]toleft[i]andright[i]for eachi, where bothleft[i]andright[i]are non-zero. This condition ensures that we only consider valid sequences whereprices[i]is less thanprices[j]and less thanprices[k]. The maximum sum obtained from this step represents our answer, with-1returned 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.
Which one best describes the time complexity of the following code?
1int factorial(int n) {
2 if (n < 0) {
3 return -1;
4 } else if (n == 0) {
5 return 1;
6 } else {
7 return n * factorial(n - 1);
8 }
9}
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]remains0. - At
prices[1] = 4, the left maximum profit is1(the profit of the previous lower priced item), so we updateleft[1] = 1. - At
prices[2] = 5, the left maximum profit is2(the profit of the previous lower priced item atprices[1]), soleft[2] = 2. - At
prices[3] = 1, this item's price is lower than all previous items, soleft[3]remains0. - At
prices[4] = 6, the left maximum profit is3(previous lower priced item's profit atprices[2]), soleft[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]remains0. - At
prices[3] = 1, since no higher priced items have been encountered yet,right[3]remains0. - At
prices[2] = 5, the right maximum profit is5(the profit of next higher priced item atprices[4]), soright[2] = 5. - At
prices[1] = 4, the right maximum profit is5, soright[1] = 5. - At
prices[0] = 3, the right maximum profit is5, soright[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 haveleft[0] = 0andright[0] = 5. Sinceleft[0]is zero, we ignore this. - For
prices[1] = 4, we haveleft[1] = 1andright[1] = 5. The total profit is1 + 2 + 5 = 8. - For
prices[2] = 5, we haveleft[2] = 2andright[2] = 5. The total profit is2 + 3 + 5 = 10. - For
prices[3] = 1,left[3]andright[3]are both zero, so we ignore this. - For
prices[4] = 6,left[4] = 3andright[4] = 0. Sinceright[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 )
591class 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}
771#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};
741// 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}
69What is the space complexity of the following code?
1int sum(int n) {
2 if (n <= 0) {
3 return 0;
4 }
5 return n + sum(n - 1);
6}
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.
What's the relationship between a tree and a graph?
Recommended Readings
Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
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 algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching 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.