Leetcode 121 - Best Time to Buy and Sell Stock
Explanation for Leetcode 121 - Best Time to Buy and Sell Stock problem, and its solution in Python.
Problem
Leetcode 121 - Best Time to Buy and Sell Stock
Example:
1
2
3
4
5
6
7
8
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.
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
Approach
Brute force way of solving this problem is to check every possible pair of buy and sell days and return the maximum profit. However, this approach has a time complexity of O(n^2) because we are checking every pair of days. We can improve this to be better by using other approaches.
We can keep track of the minimum price and the maximum profit. As we iterate through the prices, we update the minimum price and calculate the profit at each day(index). Then we update the maximum profit if the current profit is greater than the maximum profit.
Visual representation of the approach:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
prices = [7,1,5,3,6,4]
lowest_price = 7
max_profit = 0
prices[1] = 1
lowest_price = 1
max_profit = 0
prices[2] = 5
lowest_price = 1
max_profit = 4 Since 5 - 1 = 4, which is greater than 0
prices[3] = 3
lowest_price = 1
max_profit = 4 Since 3 - 1 = 2, which is less than 4
prices[4] = 6
lowest_price = 1
max_profit = 5 Since 6 - 1 = 5, which is greater than 4
prices[5] = 4
lowest_price = 1
max_profit = 5 Since 4 - 1 = 3, which is less than 5
Thus, max_profit = 5
Here’s the implementation of the above approach:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# initialize lowest price to the first price in the list, and max profit to 0
lowest_price = prices[0]
max_profit = 0
# iterate through the prices
for price in prices:
if lowest_price > price:
lowest_price = price
# update the max profit if the current profit is greater
max_profit = max(max_profit, price - lowest_price)
return max_profit
Time Complexity and Space Complexity
The time complexity is $ O(n) $ since we are iterating through the prices array once.
The space complexity is $ O(1) $ since we are not using any additional space.