0121. Best Time to Buy and Sell Stock

Easy | Array + DP | 796 ms (96.38%), 22.7 MB (60.86%)

❓ Problem Statement

Source: LeetCode - Best Time to Buy and Sell Stock GitHub: Solution / Performance

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

✍🏻 Constraints & Example

Constraints:

• 1 <= prices.length <= 10^5

• 0 <= prices[i] <= 10^4

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note: Buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

💡 Ideas

We can use Final State Machine to solve the series of these problems.

Note that this problem limits us to do only one transaction, so, for each calculation of hold state's profit, previous no-hold state's profit is 0.

In other words, the only possible situation at the no-hold state is that we haven't done any transactions yet. Thus, the profit is zero.

• Hold state means you hold the stock.

  • Since you don't have any stocks at the beginning, the profit at this state is initialized with negative infinity.

  • The profit in this state is calculated by: previous no-hold state's profit - current stock price (= buy) = 0 - current stock price

• No-Hold state means you do not hold any stocks.

  • Since you don't have any stocks at the beginning (you're initially at this state ), the profit at this state is initialized with 0.

  • The profit in this state is calculated by: previous hold state's profit + current stock price (= sell)

  • Return the profit at the no-hold state as the maximum profit since the hold state still has stock on hold.

🤖 Python3

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        #  (base case)
        if len(prices) == 0 or len(prices) == 1: return 0
        
        # ==================================================
        #  Array + Dynamic Programming              (FSM)  =
        # ==================================================
        # time  : O(n)
        # space : O(1)
        
        hold, noHold = float('-inf'), 0
        
        for price in prices:
            preHold, preNoHold = hold, noHold
            
            #  HOLD    state - (1) no transaction in HOLD state    (2) BUY at NO HOLD state
            #  [Note] NO HOLD state has no profit since only allow one transaction
            hold   = max(preHold,   0         - price)
            
            #  NO HOLD state - (1) no transaction in NO HOLD state (2) SELL at HOLD state
            noHold = max(preNoHold, preHold   + price)
        
        #  (HOLD state does not have MAX profit)
        return noHold

🤖 Java

class Solution {
    /**
     * @time  : O(n)
     * @space : O(1)
     */
     
    public int maxProfit(int[] prices) {
        /* base case */
        if(prices.length == 1) return 0;
        
        int hold = Integer.MIN_VALUE, noHold = 0;
        for(int price: prices) {
            int preHold = hold, preNoHold = noHold;
            
            hold = Math.max(preHold, 0 - price);
            noHold = Math.max(preNoHold, preHold + price);
        }
        
        return noHold;
    }
}