121. Best Time to Buy and Sell Stock — LeetCode(Python)
I got you!
Problem:
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 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 <= 1050 <= prices[i] <= 104
Solution:
l, r = 0, 1
max_profit = 0
while r < len(prices):
profit = prices[r] - prices[l]
max_profit = max(max_profit, profit)
if profit < 0:
l = r
r += 1
return max_profitExplanation —
We use a two-pointer sliding window technique here.
We initialize two pointers at the first two indices of the array prices. These pointers point towards our buy and sell days respectively.
We iterate through the array, and keep storing the profit, selling on a given day would lead to.
This profit, is then compared to the maximum profit thus far, and updates to our max_profit are made if required.
If, however, we encounter a day which has a lower buying point than the previous one, i.e. the profit becomes negative, we update our l pointer to point to this new lowest point.
The window is slid one element in the array at a time, and finally our max_profit is returned.
Time and Space Complexity —
Since traversing through the array once is a linear time operation, we can say that our code requires linear time to run.
Also, we are using only constant extra space here.
Thus, if n is the length of the array prices,
Time Complexity: O(n)
Space Complexity: O(1)
