O(1) space, O(N) complexity algorithm for buy and sell stock twice interview question

Question: Given a time series of stock prices, what is the maximum profit you can make if you are allowed to Buy and sell the stock twice. The second buy has to come after first sell.

Solution: There is a O(N) time and O(N) space complexity solution, that keeps track of the maximum profit that can be made when selling at day i in a N size array. Then it calculates the max profit by using this array in conjunction with max profit that can be made by buying at day i+1.

I would appreciate any hints on how I can get a O(N) time and O(1) space complexity solution?

Here's an O(1) space, O(n) time algorithm with Java code.

Logic:

Let $P_i$ denote the price of the stock on day $i$.

• Calculate maximum profit for $1^{st}$ transaction by $selling$ at or before day $i$ the usual way i.e. by calculating $Max(P_i - min[P_0...P_{i-1}])$. Call this $MaxProfit1_i$.

• If you had sold before day $i$ you can buy again at day $i$. If you do so, you'll need to deduct day $i$'s price from the 1st transaction's profit. Then, the maximum leftover profit at day $i$ is $Max(P_i - MaxProfit1_i)$. Call this $MaxLeftOver_i$.

• In the same vein, if you had bought the 2nd stock before day $i$, you can sell it at day $i$. If you do so, you add

day $i$'s price to the previous leftover profit to arrive at your profit at day $i$ with 2 transactions. Then, the maximum profit at day $i$ with 2 transactions is $Max(P_i + MaxLeftOver_i)$ - which is the final answer.

public int maxProfitWith2Transactions(int[] prices) {
if (prices.length == 0) return 0;

int minPrice = prices[0];
int maxProfitAfterFirstSell = 0;
int maxProfitLeftAfterSecondBuy = Integer.MIN_VALUE;
int maxProfitAfterSecondSell = 0;

for(int i = 1; i

The below modified (slightly faster) variant of the above beats every solution in both space and time on LeetCode.
public int maxProfitWith2Transactions(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfitAfterFirstSell = 0;
int maxProfitLeftAfterSecondBuy = Integer.MIN_VALUE;
int maxProfitAfterSecondSell = 0;

for(int p : prices) {
minPrice = Math.min(p, minPrice);
maxProfitAfterFirstSell = Math.max(p - minPrice, maxProfitAfterFirstSell);
maxProfitLeftAfterSecondBuy = Math.max(maxProfitAfterFirstSell - p, maxProfitLeftAfterSecondBuy);
maxProfitAfterSecondSell = Math.max(p + maxProfitLeftAfterSecondBuy, maxProfitAfterSecondSell);
}
return maxProfitAfterSecondSell;
}


Here's the values that the above code calculates for prices 8, 10, 3, 7, 4, 9, 2, 3`.
Clearly, the max profit after 1 transaction is 6 (Buy at 3, sell at 9). After 2 transactions, the max profit is 9 (Buy at 3, Sell at 7, Buy again at 4, sell at 9).

$$\begin{array}{l|r r r r r r r r}
\text{$i$} & \text{0} & \text{1} & \text{2} & \text{3} & \text{4} & \text{5} & \text{6} & \text{7} \\ \hline
\text{Price} & \text{8} & \text{10} & \text{3} & \text{7} & \text{4} & \text{9} & \text{2} & \text{3} \\ \\ \hline
\text{Lowest price seen} & \text{8} & \text{8} & \text{3} & \text{3} & \text{3} & \text{3} & \text{2} & \text{2} \\
\text{till day $i$} \\ \hline
\text{Max Profit if} & \text{x} & \text{2} & \text{2} & \text{4} & \text{4} & \text{6} & \text{6} & \text{6} \\
\text{bought at lowest} \\
\text{price before day $i$} \\
\text{and sold before} \\
\text{or on day $i$} \\ \hline
\text{Max Profit left if} & \text{x} & \text{-8} & \text{-1} & \text{-3} & \text{0} & \text{0} & \text{4} & \text{4} \\
\text{2nd buy is done on} \\
\text{day $i$.} \\
\text{= Max(PreviousRow$_i$ - $P_i$)} \\ \hline
\text{Max Profit if 2nd} & \text{x} & \text{2} & \text{2} & \text{4} & \text{6} & \text{9} & \text{9} & \text{9} \\
\text{stock is sold before} \\
\text{or on $P_i$} \\
\text{= Max(PreviousRow$_i$ + $P_i$)} \\ \hline
\end{array}$$

StackExchange Computer Science Q#60668, answer score: 8