LeetCode #121 Best Time to Buy and Sell Stock

Posted on | Post modified | In , , , , , , ,

Problem

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

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Examples

1
2
3
4
Input: [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.
             Not 7-1 = 6, as selling price needs to be larger than buying price.
1
2
3
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Solution1

Method: Greedy

Time Complexity: O(n^2)

Space Complexity: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        prices_w_date = [(idx, price) for idx, price in enumerate(prices)]
        prices_w_date.sort(key = lambda x: x[1])
        profit = 0
        data_size = len(prices_w_date)
        
        for idx, (date, price) in enumerate(prices_w_date):
            for idx_j in range(data_size - 1, idx, -1):
                if date > prices_w_date[idx_j][0] or \
                   price > prices_w_date[idx_j][1]:
                    continue
                else:
                    if prices_w_date[idx_j][1] - price > profit:
                        profit = prices_w_date[idx_j][1] - price
                        break
        
        return profit

Solution2

Method: Dynamic Programming

Time Complexity: O(n)

Space Complexity: O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        min_price = float('inf')
        max_profit = 0

        for price in prices:
            if price < min_price:
                min_price = price
            else:
                if price - min_price > max_profit:
                    max_profit = price - min_price
        
        return max_profit