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

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?

Answer 1

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 < prices.length; i++) {
        final int p = prices[i];
        maxProfitAfterFirstSell     = Math.max(p - minPrice, maxProfitAfterFirstSell); 
        minPrice                    = Math.min(p, minPrice); 
        maxProfitLeftAfterSecondBuy = Math.max(maxProfitAfterFirstSell - p, maxProfitLeftAfterSecondBuy); 
        maxProfitAfterSecondSell    = Math.max(p + maxProfitLeftAfterSecondBuy, maxProfitAfterSecondSell); 
    }
    return maxProfitAfterSecondSell;
}

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}$$

Answer 2

Hints:

The goal is to pick four values from the sequence such that

$$\frac{v_j}{v_i}\frac{v_l}{v_k}$$ is maximized. The solution is made of the two ratios that fulfill the order constraint while maximizing the product.

The best ratio in an interval is given by the maximum over the minimum, which you can find in time proportional to the interval size. You can also update the best ratio incrementally when you lengthen the interval, by recomputing the minimum and maximum.

If you sweep the whole array, you can obtain the best ratios on the left and right subarrays and compute their product. This is done in linear time on the left side (incrementally). So far, I have not found the trick to achieve linear time on the right (because the interval shrinks rather than lengthens).

Answer 3

At any point in time, you have either (a) not bought anything, (b) bought stock once, (c) bought and sold stock once, (d) bought and sold, then bought again, (e) bought and sold twice. In each case you have a certain amount of cash and a certain number of shares. Initially, you have all cash and zero shares in state (a); to simplify the algorithm assume that you might be in states (b) to (e) with a buy/sell of zero shares.

At each point when the share price is known, you could switch say from state (a) to (b), and you do that if the result is better than a previous state (b). Or switch from state (b) to (c) etc. You need only a fixed amount of memory for these five states, and O (n) comes from processing n new share prices.

Answer 4

denote d[n] as array. index from 0 ~ e  where e = (n - 1)  
trans(i, j) = max(d[k2] - d[k1])  subject to:  k2 > k1 and k2 <= j  k1 >= i  
k1, k2 = argmax(trans(i, j))  k1 means buy point   k2 means sold point  
split(k) = trans(0, k) + trans(k+1, e)
we need to get max(split(k), subject to: 0 <= k <= e)

(1) caculate: i, j =  argmax(trans[0, e])
note the property:
     d[k] > d[i]  when k < i
     d[k] < d[j]  when k > j
     d[i] < d[k] < d[j] when i < k < j  

(2) easy to prove:
    split(k) <= split(i) when k <= i  
    split(k) <= split(j) when k >= j  
    caculate: trans(0, i-1) and trans(j+1, e)  

(3) caculate  split(k)  when  i < k < j  
   split(k) = trans(0, k) + trans(k+1, e)  
   consider:  
   trans(0, k) , A if sold before i,  trans(0, k) = trans(0, i-1)
                 B if sold after i, must buy  i  

   consider:
   trans(k+1, e), C if buy after j, trans(k+1, e) = trans(j+1, e)  
                  D if buy before j, must sold j  

   consider  all casees:
   split(k) = max( A + C, A + D, B + C, B + D)  
   A + C = tran(0, i - 1) + trans(j+1, e)  
   B + D,  a similary problem:   sold max and buy min between d[i+1] , d[j-1], will token o(n) time complexity  
   A  + D /  B + C   we   iterate on all possible k