Best Time to Buy and Sell Stock

Problem Statement

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

You may choose a single day to buy one PythonCoin and choose a different day in the future to sell it.

Return the maximum profit you can achieve. You may choose to not make any transactions, in which case the profit would be 0.

Example 1:

Input: prices = [10,1,5,6,7,1]


Output: 6

Explanation: Buy prices[1] and sell prices[4], profit = 7 - 1 = 6.

Example 2:

Input: prices = [10,8,7,5,2]


Output: 0

Explanation: No profitable transactions can be made, thus the max profit is 0.

Constraints:

  • 1 <= prices.length <= 100
  • 0 <= prices[i] <= 100

You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.

You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.

Hint 1

A brute force solution would be to iterate through the array with index i, considering it as the day to buy, and trying all possible options for selling it on the days to the right of index i. This would be an O(n^2) solution. Can you think of a better way?

Hint 2

You should buy at a price and always sell at a higher price. Can you iterate through the array with index i, considering it as either the buying price or the selling price?

Hint 3

We can iterate through the array with index i, considering it as the selling value. But what value will it be optimal to consider as buying point on the left of index i?

Hint 4

We are trying to maximize profit = sell - buy. If the current i is the sell value, we want to choose the minimum buy value to the left of i to maximize the profit. The result will be the maximum profit among all. However, if all profits are negative, we can return 0 since we are allowed to skip doing transaction.

Solution

Brute Force

def max_profit_brute_force(prices: List[int]) -> int:
    res = 0
    for i in range(len(prices)):
        buy = prices[i]
        for j in range(i + 1, len(prices)):
            sell  = prices[j]
            res = max(res, sell - buy)
    return res

Time complexity: O(n^2) Space complexity: O(1)

Two Pointers

def max_profit_two_pointers(prices: List[int]) -> int:
    left, right = 0, 1
    max_profit = 0


    while right < len(prices):
        if prices[left] < prices[right]:
            profit = prices[right] - prices[left]
            max_profit = max(max_profit, profit)
        else:
            left = right
        right += 1
    return max_profit

Time complexity: O(n) Space complexity: O(1)

Dynamic Programming

def max_profit_dynamic_programming(prices: List[int]) -> int:
    max_profit = 0
    min_buy = prices[0]


    for sell in prices:
        max_profit = max(max_profit, sell - min_buy)
        min_buy = min(min_buy, sell)
    return max_profit

Time complexity: O(n) Space complexity: O(1)