I’ve recently begun tackling the Blind 75, a curated list of LeetCode problems put together by Yangshun Tay, aimed at aiding those prepping for software engineering interviews. Writing these posts not only reinforces my understanding but also, I hope, aids others working through the list.
I would like to shoutout NeetCode. If I ever ran into a problem that I just couldn’t wrap my head around, I could always count on his channel as he consistently offers videos that break down the problem that guides you to your solution.
Today, we are looking at LeetCode 121: Best Time to Buy and Sell Stock
LeetCode Description
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.
Examples
Input: prices = [7,1,5,3,6,4]
Output: 5The best strategy is to buy on day 2 (price = 1) and sell on day 5 (price = 6) which gives a profit of 6-1=5.
Input: prices = [7,6,4,3,1]
Output: 0No profit can be made, so the result is 0.
Initial Intuition
When we first read the problem, it might seem tempting to use a brute-force approach: compare the prices of each pair of days (i.e., for every day, check how much profit could be earned if the stock was sold on every future day). However, with this method, the time complexity can become O(n^2) for n days, which would be quite slow for larger inputs.
Optimized Approach
To maximize profit on any given day, it’s crucial to identify the lowest price from all preceding days, considering it as the potential buying day. As we iterate through the prices list:
- We use the buy variable to reference the index of the lowest price we’ve seen so far; initially set to the beginning of prices (index 0).
- For each new day (or price), we calculate the potential profit by selling on that day and buying on the previously found lowest-priced day.
- If we encounter a day with a price lower than our stored buy day, we update buy to this day’s index.
Solution
class Solution:
def maxProfit(self, prices: List[int]) -> int:
maxProfit = 0
buy = 0 # Initial buying day is at index 0 of prices
for sell in range(1, len(prices)):
# Update max profit with potential profit of selling today
maxProfit = max(maxProfit, prices[sell] - prices[buy])
# Update buying day if a cheaper price is found
if prices[sell] < prices[buy]:
buy = sell
return maxProfitTime and Space Complexity
The time complexity of this solution is O(n), where n is the length of the prices list. This is because we only traverse the list once.
The space complexity is O(1) as we are using a constant amount of space regardless of the input size.