This article is another part of a series on leet code problems solutions, and it provides a solution to the leet code problem 121. This is a Leet code problem named Best Time to Buy and Sell Stock. We will solve it using python and it is the best space and time-optimized solution.
Question of Best Time to Buy and Sell Stock
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
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
Approach to solve Best Time to Buy and Sell Stock
We will use simple array traversing approach. While traversing we just check for minimum buying price and maximum selling price after that buying price. After this we simply calculate the maximum profit for stocks.
Variables and its usage
We will use four variables here to complete our code:
buy – this variable to store minimum buying price.
sell – this variable to store maximum selling price.
profit – this variable is used to store maximum profit throughout the array.
profit_so_far – this variable is used to store current profit in for loop each time.
Algorithm
This method performs the following steps for a given input array:
Initialize buy price as 0th element of prices array.
Initialize sell with 0
Initialize profit with 0.
Initialize profit_so_far with 0.
Run for loop from 1 to length of prices array.
Store current price in variable pr.
check if the current price is less than the buy price.
If yes then store pr in buy and sell.
Check sell price is less than pr.
If yes then sell price will be equal to pr.
Check current profit by taking the difference of sell and buy and storing it in variable profit_so_far.
If current profit is greater than profit
Then store profit
End For
Return Profit
Python Code for Best Time to Buy and Sell Stock
def maxProfit( prices ) :
#variable to store minimum buying price
buy = prices[0]
# variable to store maximum selling price
sell = 0
#used to store maximum profit throughout the array
profit = 0
# to store current profit
profit_so_far = 0
for i in range(1,len(prices)):
pr = prices[i]
# check if current price is less than buy price
if(pr < buy):
# if yes then store pr in buy sell
buy =sell =pr
# check sell price is less than pr
elif(sell < pr):
# if yes than sell price will be equal to pr
sell = pr
# Check current profit
profit_so_far = sell-buy
# If current profit is greater than profit
if(profit_so_far > profit):
# store profit
profit = profit_so_far
return profit
prices = [7,6,4,3,1]
print(maxProfit( prices ))
prices = [7,1,5,3,6,4]
print(maxProfit( prices ))
