Connecting the O(1) space and O(N) space solutions


  • 0
    J

    I have been reading the solutions, it seems to be two popular ones. One is the ordinary dp which uses O(N) space, other "not so dp" one uses O(1) space. Let me try to explain why these two solution are actually the same conceptually.

    Here is the ordinary dp solution (inspired by @peterleetcode, i rewrote it in python )

    def maxProfit(self, prices):
        n = len(prices)
        if n < 2:
            return 0
        
        dp = [ [0] * n for _ in range(3) ]
        
        for i in range(1, 3):
            best_entry = dp[i-1][0] - prices[0]
            for j in range(1, n):
                dp[i][j] = max(dp[i][j-1], best_entry+ prices[j])
                best_entry = max(best_entry, dp[i-1][j] - prices[j])    
        return dp[-1][-1]
    

    The logic is clear, we are keeping a 3xn matrix and update it row by row. dp[i][j] represents the best profit with at most "i" trades until the "j"th price. dp[0][:] is just a dummy row with all "0", since it represents profit with at most "0" trades. At dp[i][j], we determine the best entry point using dp[i-1][:j] (in finance terms: buying the stock = entering the position).

    The following plot illustrates the update process:
    0_1508082427247_best_time_buy_sell_stock_III.png

    Note that instead of update row by row, if we update it column by column, we just need dp[:][j-1] to update dp[:][j]. Therefore we only need to store the previous column, so we have O(1) space. Update process in the following graph, notice that we only need to keep the "green balls":
    0_1508082616744_best_time_buy_sell_stock_III (1).png

    Rewrote it with this idea, the solution now becomes exactly the same as the O(1) solutions on the forum.

    def maxProfit(self, prices):
        n = len(prices)
        if n < 2:
            return 0
        
        best_entry0, best_entry1 = -prices[0], -prices[0]
        dp1, dp2 = 0, 0
        
        for p in prices[1:]:
            dp1 = max(dp1, p + best_entry0)
            best_entry0 = max(best_entry0, -p)
            best_entry1 = max(best_entry1, dp1 - p)
            dp2 = max(dp2, p + best_entry1)
    
        return dp2
    

    Hope it helps, happy leetcoding


Log in to reply
 

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