121. Best Time to Buy and Sell Stock

Question

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

Example 1

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 that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Solution 1: Brute Force (TLE)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        ans = 0
        for i in range(n - 1):
            for j in range(i + 1, n):
                if prices[j] > prices[i]:
                    ans = max(ans, prices[j] - prices[i])
        return ans

Time Complexity: O(N^2)
Space Complexity: O(1)

Solution 2: For-Loop

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        maxProfit = 0
        localMin = 0x3f3f3f3f
        for v in prices:
            localMin = min(localMin, v)
            maxProfit = max(maxProfit, v - localMin)
        return maxProfit

Time Complexity: O(N)
Space Complexity: O(1)

Solution 3: Two Pointer

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        maxProfit = 0
        
        idxMin = 0
        idxMax = 1
        while(idxMax < n):
            curProfit = prices[idxMax] - prices[idxMin]
            if curProfit > 0:            
                maxProfit = max(maxProfit, curProfit)
            else:
                idxMin = idxMax
            idxMax += 1
        
        return maxProfit

Time Complexity: O(N)
Space Complexity: O(1)

Reference

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/discuss/1735550/Python-Javascript-Easy-solution-with-very-clear-Explanation

Follow-up: Best Time to Buy and Sell Stock II

Follow-up 2: Best Time to Buy and Sell Stock III

Follow-up 3: Best Time to Buy and Sell Stock IV

TODO

Time Complexity: O()
Space Complexity: O()