LeetCode Best Time to Buy and Sell Stock III: O(N) Time and O(1) Space

Overview

Dynamic Programming (DP) is used to solve this LeetCode Best Time to Buy and Sell Stock III and O(1) space could be achieved from another angle.

LeetCode Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution Analysis: O(N) Time and O(1) Space

1) Brute Force O(N^2) time: We need to use divide and conquer, suppose the transactions are performed separately in sub sequence [0..i] and [i..n-1] both inclusive because it would also be possible a single transaction if the customer actually sell the stock in the morning at day i and buy a new one in the afternoon at day i (it is required at most two transactions rather than exactly two transactions). So for all such i’s we find the maximum profits in the two parts and from  ”leetcode: Best Time to Buy and Sell Stock II”  we know this could be done in O(N) time, for all such i’s the total time complexity would be O(N^2)

2) 3 passes processing O(N) time and O(N) space: One might easily come up with a naive algorithm based on the “leetcode: Best Time to Buy and Sell Stock II“ problem (I am one of them >_<), that is, find the maximum profit and second maximum profit among all the increasing intervals and add them together. This is wrong, and one counter example is: 7 9 6 1 3 2 4 7 –> [7, 9] = 2 [1,  3] = 2   [2, 7] = 5, so previous algorithm will yield 2 + 5 = 7, however, obviously, (9-7) + (7-1) = 8 is a better one. This is quite different from  ”leetcode: Best Time to Buy and Sell Stock II“ because now we are restricted to use at most two transactions!

However, the correct solution is indeed based on some previous algorithm, it is based on a similar idea in “leetcode: Best Time to Buy and Sell Stock“. The general approach is divide and conquer same as in (1) but we could save all the intermediate results for later usages so we save the computation and for all i’s we take constant time to get the maximum profits in the 3rd pass. More concretely, we divide the prices into [0, i] and [i, N-1] two subsets, and get the maximum profits in [0, i] and [i, N-1]. We only need one linear scan to get maximum profits in [0, i] where i is from 0 to N-1, and a second linear scan to get profits in [i, N-1] where i is again from 0 to N-1 but in a reversed way as in the first linear scan. The linear scan algorithm is exactly the same as in “leetcode: Best Time to Buy and Sell Stock“ Lastly, we do a third linear scan to test the sum of profit[0, i] + profit[i, N-1] where i is from 0 to N-1 and we get the global maximum profit. The following code implements this idea and could pass the LeetCode Best Time to Buy and Sell Stock III in the OJ:

class Solution {
public:
int maxProfit(vector<int> &prices) {
    int n = prices.size();
    if (n < 2) return 0;

    int *profits1 = new int[n];
    int *profits2 = new int[n];

    memset(profits1, 0, sizeof(int) * n); //
    memset(profits2, 0, sizeof(int) * n); //
    int ret = 0;

    int minPrice = prices[0];
    for (int i = 1; i < n; ++i) {
        minPrice = min(minPrice, prices[i]);
        profits1[i] = max(profits1[i - 1], prices[i] - minPrice);
    }

    int maxPrice = prices[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        maxPrice = max(maxPrice, prices[i]);
        profits2[i] = max(profits2[i + 1], maxPrice - prices[i]);
    }

    // 3rd pass
    for (int i = 0; i < n; ++i)
        ret = max(ret, profits1[i] + profits2[i]);</pre>
     
    delete [] profits1;
    delete [] profits2;

    return ret;
}
};

3) “Ceiling Method” with O(N) time and O(1) Space: While the above approach (2) might be the most popular one and could be derived from the brute force method, it would be difficult to reduce the memory into O(1) because we need to store all the one transaction profits for later usage. We need to think about how to tackle this problem from another different angle: we keep  the current profits and initially it is 0 indicating we earn nothing from the stock transactions. There could be 4 different status for our profits during the whole processing

  1. buy[0]: we bought the stock as the beginning of the first transaction. Our profit would be the initial value 0 – prices[i]
  2. sell[0]: we sell the stock  in the first transaction. Our profits would be buy[0] + prices[i]
  3. buy[1]: we bought the stock as the beginning of the second transaction. Similarly, our profit would be sell[0] – prices[i]
  4. sell[1]: we sell the stack in the second transaction. So our profits would now be buy[1] + prices.

So how can we achieve our final maximum profit result? The idea is to test buying or selling stocks at each day and update the above 4 status to set it to the maximum value. Originally, the buy[0] and buy[1] status should be INT_MIN because we do not have any money to buy, so this operation would make our profit negatively maximum. And the order to update all these four values is determined because we cannot sell before buy the 1st or 2nd stocks. So the following code implements this idea:

class Solution {
public:
  int maxProfit(vector<int> &prices) {
    int n = prices.size();
    if (n < 2) return 0;

    int buy[2];
    buy[0] = buy[1] = INT_MIN;
    int sell[2];
    sell[0] = sell[1] = 0;

    for (int i = 0; i < n; ++i) {
        sell[1] = max(sell[1], buy[1] + prices[i]);
        buy[1] = max(buy[1], sell[0] - prices[i]);
        sell[0] = max(sell[0], buy[0] + prices[i]);
        buy[0] = max(buy[0], 0 - prices[i]);
    }
    return sell[1];
}
};

Reference: This idea is motivated originally from “LeetCode Discussion

Summary

Dynamic Programming (DP) is used to solve this LeetCode Best Time to Buy and Sell Stock III and O(1) space could be achieved from another angle.

Written on January 24, 2013