Solution by theGhost


  • 0
    T

    Approach#1: Brute-force [Time Limit Exceeded]

    Intuition and algorithm

    This problem is similar to the buy and sell stocks problem, except that it has constraint of only 2 max transactions allowed. Let us try to break down the problem. Can we find the maximum profit that can be made from a given set of stock prices with just one transaction ?
    We start with a buy-price at stock price index i and keep on updating the buying index when we encounter a lower buy price. Similarly we keep on updating the sell-price index when we encounter a higher price or if the current sell-index is lower than the buy-index.

    We can find the best profit possible from a set of stock prices with the inclusive ranges [s, e] as follows:

    Java

    
    int profitSingleTransaction(int[] prices, int s, int e) {
    
        int buyIdx = s, sellIdx = s+1;
    
        int maxProfit = 0;
    
        if(s >= e)
            return maxProfit;
    
    
        for(int i=s+1; i<=e; i++) {
            
            maxProfit = Math.max(maxProfit, prices[sellIdx] - prices[buyIdx]);
    
            buyIdx = (prices[i] < prices[buyIdx]) ? i: buyIdx;
    
            sellIdx = (prices[i] > prices[sellIdx] || sellIdx < buyIdx) ? i : sellIdx;
    
        }
    
        return Math.max(maxProfit, prices[sellIdx] - prices[buyIdx]);
        
    }
    
    

    Now to find the maximum profit with 2 transactions, we can think of partitioning the given stock prices into 2 groups at index mid. Then iterating over the stock prices for various partitions, we just find the best possible profit.

    Java

    
    public int maxProfitTwoTransactions(int[] prices) {
    
        int maxProfit = 0;
    
        if(prices == null || prices.length == 0)
            return maxProfit;
    
        int n = prices.length;
    
        for(int mid = 1; mid < n; mid++) {
            maxProfit = Math.max(
                    maxProfit,
                    profitSingleTransaction(prices, 0, mid) + profitSingleTransaction(prices, mid+1, n-1)
            );
        }
    
        return maxProfit;
    }
    
    

    Complexity Analysis

    *Time Complexity: O(N ^ 2) where N is the number of elements in prices

    *Space Complexity: O(1) since the only value we're storing is maxProfit

    Approach#2: State-based mathematical approach [Accepted]

    Intuition and algorithm

    On each day we can do following operations, firstBuy, firstSell, secondBuy or secondSell. Unless we've bought any stock, any price would seem lucrative/profitable, hence we start with the least possible value as our firstBuy i.e. Integer.MIN_VALUE similarly for secondBuy. We only sell when there is some profit at current price i.e. prices[i].

    Now comes the tricky part. The (secondBuy, secondSell) are initially equivalent to (firstBuy, firstSell), hence if it's possible to carry out only one transaction, we're still returning the correct maximum profit with secondSell. However, only when we've performed first buy-sell transaction, does secondBuy = Math.max(secondBuy, firstSell - prices[i]) actually makes sense, which implies we're using the profit earned from our first transaction to execute the secondBuy.

    Intuitively, when only one profitable transaction is feasible, then firstBuy, firstSell and secondBuy, secondSell are indeed the same. However, in other scenarios we're using the profit from first transaction to execute the secondBuy and both the transactions are exclusive.

    Java

    
    int maxProfit(int[] prices) {
    
        if(null == prices)
            return 0;
    
        int firstSell = 0, secondSell = 0, firstBuy = Integer.MIN_VALUE, secondBuy = Integer.MIN_VALUE;
    
        for(int i = 0; i < prices.length; i++) {
    
            firstBuy = Math.max(firstBuy, -prices[i]);
            firstSell = Math.max(firstSell, firstBuy + prices[i]);
    
            secondBuy = Math.max(secondBuy, firstSell - prices[i]);
            secondSell = Math.max(secondSell, secondBuy + prices[i]);
    
        }
    
        return secondSell;
    }
        
    

    Complexity Analysis

    • Time Complexity: O(N) where N is the number of stock prices, since we're iterating over the prices once

    • Space Complexity: O(1) since we're storing a fixed number of variables (i.e firstBuy, firstSell, secondBuy, secondSell)

    Analysis compiled by theGhost


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.