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.
Recommended Time and Space Complexity
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)