LC 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.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0

Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

Links

Question here and solution here

Solution

concept

We will use a two-pointer method to solve this problem. Left pointer = buy, Right pointer = Sell Fix a buy price and find the maximum sell price, if detected a price that is lower than the current buy price, update the buy price, and the current possible max profit by this buy price is recorded in max_profit

code

class Solution(object):
	"""
	two-pointers
	while loop
	"""
    def maxProfit(self, prices):
        # left pointer = buy
        # right pointer = sell
        l, r = 0, 1
        max_profit = 0

        while r < len(prices):
            if prices[l] < prices[r]:
                profit = prices[r] - prices[l]
                max_profit = max(max_profit, profit)
            else:
                l = r
            
            r += 1

        return max_profit

class Solution:
	"""
	two pointers
	for loop
	"""
	def maxProfit(self, prices: List[int]) -> int:
		profit = 0
		l = 0
		for r in range(1, len(prices)):
			if prices[r] > prices[l]:
				profit = max(profit, prices[r] - prices[l])
			else:
				l = r

		return profit

Complexity

time: $O(n)$
space: $O(1)$