0% completed
Problem Statement
You are given two 0-indexed arrays, prices
and profits
, both of length n
. There are n
items in an store where the i<sup>th</sup> item has a price of prices[i]
and a profit of profits[i]
.
You have to select three items with the following condition:
prices[i] < prices[j] < prices[k]
wherei < j < k
.- If such a selection is possible, calculate the total profit, which is
profits[i] + profits[j] + profits[k]
.
Return the maximum possible profit from this selection. If it's not possible to select three items that satisfy these conditions, return -1
.
Examples
Example 1:
- Input: prices =
[3, 1, 4, 6, 2]
, profits =[5, 2, 8, 10, 3]
- Expected Output:
23
- Explanation: The selected triplet is
(3, 4, 6)
with indices0, 2, 3
. The corresponding profits are5 + 8 + 10 = 23
.
Example 2:
- Input: prices =
[2, 7, 1, 5, 8, 10]
, profits =[3, 9, 1, 4, 7, 6]
- Expected Output:
22
- Explanation: The selected triplet is
(7, 8, 10)
with indices1, 4, 5
. The corresponding profits are9 + 7 + 6 = 22
.
Example 3:
- Input: prices =
[9, 8, 7, 6, 5]
, profits =[10, 9, 8, 7, 6]
- Expected Output:
-1
- Explanation: It is not possible to select three items such that their prices strictly increase.
Constraints:
- 3 <= prices.length == profits.length <= 2000
- 1 <= prices[i] <= 10<sup>6</sup>
- 1 <= profits[i] <= 10<sup>6</sup>
Solution
To solve this problem, the approach leverages the Binary Indexed Tree (BIT) to efficiently track and query the maximum profits that can be obtained from items with increasing prices. The idea is to calculate the maximum profit for a valid triplet of items, where the prices strictly increase. The BIT helps in maintaining and retrieving the maximum profit seen so far as we traverse the list of prices twice—once from left to right and once from right to left. The solution involves calculating the maximum profit that can be achieved from the left and right segments separately, and then combining them to find the overall maximum profit for any valid triplet.
This approach works efficiently because the BIT allows us to perform both update and query operations in logarithmic time. By maintaining two separate BITs (one for the left traversal and one for the right traversal), we can effectively find the maximum profit for any valid triplet by combining the best profits found during the left and right traversals.
Step-by-Step Algorithm
-
Initialize Variables:
- Determine the maximum value in the
prices
array and store it inmaxPrice
. This helps in setting the size of the BIT arrays. - Create two BIT arrays
bitForMaxLeft
andbitForMaxRight
, both of sizemaxPrice + 1
. These arrays will be used to store the maximum profit for different price indices during left-to-right and right-to-left traversals. - Create an array
maxLeftProfit
of the same size as theprices
array to store the maximum profit that can be obtained for the left side of each item.
- Determine the maximum value in the
-
Left-to-Right Traversal:
- Iterate Through Prices: Iterate through the
prices
array from left to right. - Calculate maxLeftProfit:
- For each price at index
i
, use thegetMaxProfit
function to query the BITbitForMaxLeft
for the maximum profit corresponding to all prices less thanprices[i]
. - Purpose of
getMaxProfit
: ThegetMaxProfit
function traverses the BIT from the given price down to 0, finding the maximum profit recorded for any price index less than the current price. This allows us to find the best profit we could have obtained before the current price point, which is essential for calculating valid triplets.
- For each price at index
- Store maxLeftProfit: Store this value in
maxLeftProfit[i]
. This represents the maximum profit we could have achieved on the left side ofprices[i]
. - Update BIT for Left Side:
- Use the
updateBIT
function to update the BITbitForMaxLeft
with the currentprices[i]
andprofits[i]
. - Purpose of
updateBIT
: TheupdateBIT
function traverses the BIT from the current price index upwards, ensuring that the maximum profit is recorded at every index touched by the current price. This operation makes sure that any future queries for maximum profit will consider this price's profit as a potential maximum.
- Use the
- Iterate Through Prices: Iterate through the
-
Right-to-Left Traversal:
- Initialize
maxTotalProfit
to-1
, which will store the maximum profit for any valid triplet found. - Iterate through the
prices
array from right to left. - For each price at index
i
, adjust the price toadjustedPrice = maxPrice - prices[i] + 1
to handle the reverse traversal in the BIT. - Reason for Adjusting the Price Index:
- When traversing from right to left, we want to find the best profit for prices that are greater than the current price (to ensure increasing order in the triplet).
- By adjusting the price using
maxPrice - prices[i] + 1
, we effectively "mirror" the index so that the BIT, which is designed to handle increasing indices naturally, can now handle decreasing price sequences properly during the reverse traversal. This trick allows the same BIT structure to be used in reverse order.
- Query the BIT
bitForMaxRight
for the maximum profit corresponding to all prices greater thanprices[i]
. - If both
maxLeftProfit[i]
and the profit found from the right traversal are greater than 0, updatemaxTotalProfit
to the sum ofmaxLeftProfit[i]
,profits[i]
, and the right profit. - Update the BIT
bitForMaxRight
with the adjusted price and the current profit.
- Initialize
-
Return Result:
- Finally, return
maxTotalProfit
, which holds the maximum profit for any valid triplet or-1
if no valid triplet was found.
- Finally, return
Algorithm Walkthrough
Input: prices = [3, 1, 4, 6, 2]
, profits = [5, 2, 8, 10, 3]
Initialization:
- maxPrice: Find the maximum value in the
prices
array.maxPrice = 6
- bitForMaxLeft: Initialize BIT array for left-to-right traversal.
bitForMaxLeft = [0, 0, 0, 0, 0, 0, 0]
- bitForMaxRight: Initialize BIT array for right-to-left traversal.
bitForMaxRight = [0, 0, 0, 0, 0, 0, 0]
- maxLeftProfit: Initialize array to store maximum profits from left side.
maxLeftProfit = [0, 0, 0, 0, 0]
- maxTotalProfit: Initialize the variable to store the result.
maxTotalProfit = -1
Left-to-Right Traversal:
-
Step 1 (i = 0, prices[0] = 3):
- Query BIT:
getMaxProfit(bitForMaxLeft, 2)
returns0
(no valid price less than 3). - Update maxLeftProfit:
maxLeftProfit[0] = 0
- Update BIT:
updateBIT(bitForMaxLeft, 3, 5)
- Start with
i = 3
, updatebitForMaxLeft[3] = max(0, 5) = 5
. - Next
i = 4
(sincei = i + (i & -i)
), updatebitForMaxLeft[4] = max(0, 5) = 5
. - End with
i = 8
which is out of bounds.
- Start with
- Updated Arrays:
bitForMaxLeft = [0, 0, 0, 5, 5, 0, 0]
maxLeftProfit = [0, 0, 0, 0, 0]
- Query BIT:
-
Step 2 (i = 1, prices[1] = 1):
- Query BIT:
getMaxProfit(bitForMaxLeft, 0)
returns0
(no valid price less than 1). - Update maxLeftProfit:
maxLeftProfit[1] = 0
- Update BIT:
updateBIT(bitForMaxLeft, 1, 2)
- Start with
i = 1
, updatebitForMaxLeft[1] = max(0, 2) = 2
. - Next
i = 2
, updatebitForMaxLeft[2] = max(0, 2) = 2
. - Next
i = 4
, updatebitForMaxLeft[4] = max(5, 2) = 5
(no change). - End with
i = 8
which is out of bounds.
- Start with
- Updated Arrays:
bitForMaxLeft = [0, 2, 2, 5, 5, 0, 0]
maxLeftProfit = [0, 0, 0, 0, 0]
- Query BIT:
-
Step 3 (i = 2, prices[2] = 4):
- Query BIT:
getMaxProfit(bitForMaxLeft, 3)
returns5
(best profit from price 3). - Update maxLeftProfit:
maxLeftProfit[2] = 5
- Update BIT:
updateBIT(bitForMaxLeft, 4, 8)
- Start with
i = 4
, updatebitForMaxLeft[4] = max(5, 8) = 8
. - End with
i = 8
which is out of bounds.
- Start with
- Updated Arrays:
bitForMaxLeft = [0, 2, 2, 5, 8, 0, 0]
maxLeftProfit = [0, 0, 5, 0, 0]
- Query BIT:
-
Step 4 (i = 3, prices[3] = 6):
- Query BIT:
getMaxProfit(bitForMaxLeft, 5)
returns8
(best profit from price 4). - Update maxLeftProfit:
maxLeftProfit[3] = 8
- Update BIT:
updateBIT(bitForMaxLeft, 6, 10)
- Start with
i = 6
, updatebitForMaxLeft[6] = max(0, 10) = 10
. - End with
i = 8
which is out of bounds.
- Start with
- Updated Arrays:
bitForMaxLeft = [0, 2, 2, 5, 8, 0, 10]
maxLeftProfit = [0, 0, 5, 8, 0]
- Query BIT:
-
Step 5 (i = 4, prices[4] = 2):
- Query BIT:
getMaxProfit(bitForMaxLeft, 1)
returns2
(best profit from price 1). - Update maxLeftProfit:
maxLeftProfit[4] = 2
- Update BIT:
updateBIT(bitForMaxLeft, 2, 3)
- Start with
i = 2
, updatebitForMaxLeft[2] = max(2, 3) = 3
. - Next
i = 4
, updatebitForMaxLeft[4] = max(8, 3) = 8
(no change). - End with
i = 8
which is out of bounds.
- Start with
- Updated Arrays:
bitForMaxLeft = [0, 2, 3, 5, 8, 0, 10]
maxLeftProfit = [0, 0, 5, 8, 2]
- Query BIT:
Right-to-Left Traversal:
-
Step 1 (i = 4, prices[4] = 2):
- Adjust Price:
adjustedPrice = 6 - 2 + 1 = 5
- Query BIT:
getMaxProfit(bitForMaxRight, 4)
returns0
(no valid price greater than 2). - Update BIT:
updateBIT(bitForMaxRight, 5, 3)
- Start with
i = 5
, updatebitForMaxRight[5] = max(0, 3) = 3
. - End with
i = 6
which is out of bounds.
- Start with
- Updated Arrays:
bitForMaxRight = [0, 0, 0, 0, 0, 3, 0]
maxTotalProfit = -1
(no update)
- Adjust Price:
-
Step 2 (i = 3, prices[3] = 6):
- Adjust Price:
adjustedPrice = 6 - 6 + 1 = 1
- Query BIT:
getMaxProfit(bitForMaxRight, 0)
returns0
(no valid price greater than 6). - Update BIT:
updateBIT(bitForMaxRight, 1, 10)
- Start with
i = 1
, updatebitForMaxRight[1] = max(0, 10) = 10
. - Next
i = 2
, updatebitForMaxRight[2] = max(0, 10) = 10
. - Next
i = 4
, updatebitForMaxRight[4] = max(0, 10) = 10
. - End with
i = 8
which is out of bounds.
- Start with
- Updated Arrays:
bitForMaxRight = [0, 10, 10, 0, 10, 3, 0]
maxTotalProfit = -1
(no update)
- Adjust Price:
-
Step 3 (i = 2, prices[2] = 4):
- Adjust Price:
adjustedPrice = 6 - 4 + 1 = 3
- Query BIT:
getMaxProfit(bitForMaxRight, 2)
returns10
(best profit from price 6). - Update maxTotalProfit:
maxTotalProfit = max(-1, 5 + 8 + 10) = 23
- Update BIT:
updateBIT(bitForMaxRight, 3, 8)
- Start with
i = 3
, updatebitForMaxRight[3] = max(0, 8) = 8
. - Next
i = 4
, updatebitForMaxRight[4] = max(10, 8) = 10
(no change). - End with
i = 8
which is out of bounds.
- Start with
- Updated Arrays:
bitForMaxRight = [0, 10, 10, 8, 10, 3, 0]
maxTotalProfit = 23
- Adjust Price:
-
Step 4 (i = 1, prices[1] = 1):
- Adjust Price:
adjustedPrice = 6 - 1 + 1 = 6
- Query BIT:
getMaxProfit(bitForMaxRight, 5)
returns3
(best profit from price 2). - Update maxTotalProfit:
maxTotalProfit = max(23, 0 + 2 + 3) = 23
(no change)
- Update BIT:
updateBIT(bitForMaxRight, 6, 2)
- Start with
i = 6
, updatebitForMaxRight[6] = max(0, 2) = 2
. - End with
i = 8
which is out of bounds.
- Start with
- Updated Arrays:
bitForMaxRight = [0, 10, 10, 8, 10, 3, 2]
maxTotalProfit = 23
- Adjust Price:
-
Step 5 (i = 0, prices[0] = 3):
- Adjust Price:
adjustedPrice = 6 - 3 + 1 = 4
- Query BIT:
getMaxProfit(bitForMaxRight, 3)
returns8
(best profit from price 4). maxLeftProfit[0] = 0
, which is not valid.
- Adjust Price:
Final Output:
- Return Result: The maximum profit from the valid triplet is
23
, so return23
.
Code
Complexity Analysis
Time Complexity
- The code primarily involves two operations on the Binary Indexed Tree (BIT):
updateBIT
andgetMaxProfit
. - The
updateBIT
operation takes O(\log(\text{maxPrice})) time, wheremaxPrice
is the maximum value in theprices
array. - The
getMaxProfit
operation also takes O(\log(\text{maxPrice})) time. - The solution iterates over the
prices
array twice, each time performing these operations. Therefore, the overall time complexity is O(n\log(\text{maxPrice})), wheren
is the length of theprices
array.
Space Complexity
- The space complexity is dominated by the space needed for the two BIT arrays (
bitForMaxLeft
andbitForMaxRight
), which have a size ofmaxPrice + 1
. - Additionally, an array of size
n
is used for storingmaxLeftProfit
. - Thus, the total space complexity is O(\text{maxPrice}).
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible