Solution: Best Time to Buy and Sell Stock
Problem Statement
You are given an array prices
where prices[i]
is the price of a given stock on the i^{th} 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: [3, 2, 6, 5, 0, 3]
- Expected Output: 4
- Justification: Buy the stock on day 2 (price = 2) and sell it on day 3 (price = 6). Profit = 6 - 2 = 4.
-
- Input: [8, 6, 5, 2, 1]
- Expected Output: 0
- Justification: Prices are continuously dropping, so no profit can be made.
-
- Input: [1, 2]
- Expected Output: 1
- Justification: Buy on day 1 (price = 1) and sell on day 2 (price = 2). Profit = 2 - 1 = 1.
Solution
- Understanding the Problem:
- The problem is to find the maximum difference between two numbers in an array, where the larger number comes after the smaller number.
- Approach:
- Initialize two variables,
minPrice
andmaxProfit
. - Iterate through the list of prices.
- For each price, calculate the profit that can be made by selling at that price (current price -
minPrice
). - Update
maxProfit
if the calculated profit is greater than the currentmaxProfit
. - Update
minPrice
if the current price is less thanminPrice
.
- For each price, calculate the profit that can be made by selling at that price (current price -
- Initialize two variables,
- Why This Works:
- This approach works by keeping track of the minimum price encountered so far and the maximum profit that can be made with that minimum price.
- By continuously updating these two variables, the algorithm ensures that the maximum profit is always calculated relative to the lowest price encountered so far.
Algorithm Walkthrough
Consider the input [3, 2, 6, 5, 0, 3]
:
- Initialize
minPrice
asinfinity
andmaxProfit
as0
. - Iterate through the list:
- Day 1: price is
3
minPrice
is updated to3
.- Profit =
3 - 3 = 0
.maxProfit
remains0
.
- Day 2: price is
2
minPrice
is updated to2
.- Profit =
2 - 2 = 0
.maxProfit
remains0
.
- Day 3: price is
6
minPrice
remains2
.- Profit =
6 - 2 = 4
.maxProfit
is updated to4
.
- Day 4: price is
5
minPrice
remains2
.- Profit =
5 - 2 = 3
.maxProfit
remains4
.
- Day 5: price is
0
minPrice
is updated to0
.- Profit =
0 - 0 = 0
.maxProfit
remains4
.
- Day 6: price is
3
minPrice
remains0
.- Profit =
3 - 0 = 3
.maxProfit
remains4
.
- Day 1: price is
- The final
maxProfit
is4
.
Code
Python3
Python3
. . .
You must run your code first
Complexity Analysis
- Time Complexity: O(n), where n is the number of days. This is because the algorithm iterates through the list of prices once, performing constant-time operations for each price.
- Space Complexity: O(1), as it uses a constant amount of extra space (two variables to keep track of
minPrice
andmaxProfit
).