20. Stock Buy and Sell β Max 2 Transactions Allowed
The problem can be found at the following link: Question Link
Problem Description
In daily share trading, a trader buys shares and sells them on the same day. Given an array prices[] representing stock prices throughout the day, find the maximum profit a trader could have made with at most 2 transactions.
β Note: The second transaction can only start after the first one is complete (buy β sell β buy β sell).
Examples
Example 1:
Input:
prices[] = [10, 22, 5, 75, 65, 80]
Output:
87
Explanation:
Buy at 10, sell at 22 β Profit = 12
Buy at 5, sell at 80 β Profit = 75
Total Profit = 12 + 75 = 87
Example 2:
Input:
prices[] = [2, 30, 15, 10, 8, 25, 80]
Output:
100
Explanation:
Buy at 2, sell at 30 β Profit = 28
Buy at 8, sell at 80 β Profit = 72
Total Profit = 28 + 72 = 100
Constraints:
$1 \leq \text{prices.size()} \leq 10^5$
$1 \leq \text{prices[i]} \leq 10^5$
My Approach
Optimized Greedy Approach
Use four variables:
b1
(Best price to buy first stock)s1
(Best profit after first sale)b2
(Best price to buy second stock after first sale)s2
(Best profit after second sale)
Iterate through prices and update these variables accordingly.
Return
s2
(Maximum profit with at most two transactions).
Algorithm Steps:
Initialize
b1 = β
,s1 = 0
,b2 = β
,s2 = 0
.For each price
p
in the array:Update
b1
(Minimum price to buy first stock).Update
s1
(Best profit after first sale).Update
b2
(Best price to buy second stock).Update
s2
(Best profit after second sale).
Return
s2
.
Time and Auxiliary Space Complexity
Expected Time Complexity: O(N), as we traverse the array once and perform a constant number of operations.
Expected Auxiliary Space Complexity: O(1), as we use only four variables.
Code (C++)
class Solution {
public:
int maxProfit(vector<int>& a) {
int b1 = INT_MAX, s1 = 0, b2 = INT_MAX, s2 = 0;
for (int p : a) {
b1 = min(b1, p);
s1 = max(s1, p - b1);
b2 = min(b2, p - s1);
s2 = max(s2, p - b2);
}
return s2;
}
};
Code (Java)
class Solution {
public static int maxProfit(int[] a) {
int b1 = Integer.MAX_VALUE, s1 = 0, b2 = Integer.MAX_VALUE, s2 = 0;
for (int p : a) {
b1 = Math.min(b1, p);
s1 = Math.max(s1, p - b1);
b2 = Math.min(b2, p - s1);
s2 = Math.max(s2, p - b2);
}
return s2;
}
}
Code (Python)
class Solution:
def maxProfit(self, a):
b1, s1, b2, s2 = float('inf'), 0, float('inf'), 0
for p in a:
b1, s1, b2, s2 = min(b1, p), max(s1, p - b1), min(b2, p - s1), max(s2, p - b2)
return s2
Contribution and Support:
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Letβs make this learning journey more collaborative!
β If you find this helpful, please give this repository a star! β
πVisitor Count
Last updated