121. Best Time to Buy and Sell Stock
Problem Description
The problem presents us with an array named prices
that represents the price of a certain stock on each day. Our objective is to choose a single day for buying one stock and another future day for selling that stock in order to achieve the maximum possible profit. If it's not possible to make any profit, the expected return value is 0
. This problem essentially asks us to find two days, where buying on the first and selling on the second would result in the highest profit margin.
Intuition
The intuition behind the solution revolves around evaluating the difference between buying and selling prices while also making sure that we buy at the lowest price possible before selling. The strategy is to keep track of two key variables as we iterate through the prices
array: the maximum profit found so far and the lowest price observed. We initialize the maximum profit (ans
) as 0
and the minimum price (mi
) as infinity to simulate that we haven't bought any stock yet.
As we iterate over each price in prices
, we consider it as the potential selling price and calculate the profit we would get if we bought at the lowest price seen until now (mi
). If this profit is larger than the current maximum profit (ans
), we update ans
. Regardless of whether it led to a new maximum profit or not, we then update mi
if the current price is lower than any we've seen so far.
By the end of the iteration, we will have the highest possible profit that can be made with a single transaction, which is the difference between the lowest purchasing price and the highest subsequent selling price.
Learn more about Dynamic Programming patterns.
Solution Approach
The provided solution uses a simple yet effective approach that relies on a single pass through the prices
array, a concept that is often referred to as the "One Pass" algorithm. This algorithm falls under the category of greedy algorithms since it makes a locally optimal choice at each step with the hope of finding a global optimum.
Here's a step-by-step walk-through of the implementation:
-
Initialize Variables: Two variables are initialized at the start.
ans
is initialized to0
to represent the maximum profit which starts at no profit, andmi
is set toinf
, representing the minimum buying price (set to infinity since we have not encountered any price yet). -
Iterate Over
prices
: We loop through each pricev
in the arrayprices
, treating each one as a potential selling price. -
Calculate Profit and Update Maximum Profit (
ans
): For each pricev
, if selling at this price leads to a profit higher than the best profit found so far (ans
), the maximum profit is updated. This is done by computing the differencev - mi
and using themax
function:ans = max(ans, v - mi)
. -
Update Minimum Buying Price (
mi
): After checking the potential profit at pricev
, update the minimum buying price ifv
is lower than all previously seen prices:mi = min(mi, v)
. -
Return Maximum Profit: After finishing the traversal of the array
prices
, the variableans
holds the maximum profit that can be achieved. This value is returned as the solution to the problem.
The algorithm's efficiency hinges on the fact that the maximum profit can be found by simply keeping track of the lowest price to buy before each potential selling day. It uses constant space (only two variables), and the time complexity is linear, O(n), as it requires only one pass through the list of prices, where n
is the number of prices in the input array.
This approach comes under dynamic programming as well since it essentially keeps a running track of state (in this case, the minimum element so far and the maximum profit so far), but it is the greedy aspect of choosing the current best action (buy/sell) that defines it more aptly.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's assume we have an array of stock prices for 5 consecutive days, represented as follows: prices = [7, 1, 5, 3, 6, 4]
.
Applying the solution approach step-by-step:
-
Initialize Variables: Set
ans = 0
(maximum profit starts at no profit) andmi = inf
(minimum buying price is initially set to infinity since no prices have been seen yet). -
Iterate Over
prices
Day 1 (prices[0] = 7
): Start with the first price. Sincemi
is set to infinity, any price we encounter will be lower, so we setmi = 7
. -
Day 2 (
prices[1] = 1
): Proceed to the next price.- Potential profit if we sell today:
1 - mi = 1 - 7 = -6
. Since this is negative, no profit is made. We don't updateans
. - Update
mi
since1
is less than7
:mi = 1
.
- Potential profit if we sell today:
-
Day 3 (
prices[2] = 5
): Move on to the third price.- Potential profit:
5 - mi = 5 - 1 = 4
. This is a profit, and sinceans
is0
, it becomes the new maximum profit:ans = 4
. mi
remains at1
, as5
is higher than the currentmi
.
- Potential profit:
-
Day 4 (
prices[3] = 3
): Evaluating the fourth price.- Potential profit:
3 - mi = 3 - 1 = 2
. This is less than the currentans
of4
, soans
remains unchanged. - Update
mi
to3
? No, since3
is more than the currentmi
of1
.
- Potential profit:
Day 4 (prices[3] = 3
)
6. Day 5 (prices[4] = 6
): Analyzing the fifth price.
- Potential profit:
6 - mi = 6 - 1 = 5
. This exceeds the currentans
of4
, so we updateans = 5
. mi
remains unchanged as6
is higher than1
.
-
Day 6 (
prices[5] = 4
): Finally, the price on the last day.- Potential profit:
4 - mi = 4 - 1 = 3
. This does not beat the currentans
of5
, soans
stays at5
. mi
does not change, as4
is higher than1
.
- Potential profit:
-
Return Maximum Profit: Having processed all days, we have found that the maximum profit is
ans = 5
, which is the highest profit achievable (by buying on day 2 at a price of1
and selling on day 5 at a price of6
).
The solution approach efficiently found the best day to buy and the best day to sell in a single pass through the prices
array, confirming the maximum profit of 5
for this example. The linear time complexity (O(n)) and constant space complexity are apparent, as the algorithm only needed to iterate through the array once while using two variables.
Solution Implementation
1from typing import List
2
3class Solution:
4 def maxProfit(self, prices: List[int]) -> int:
5 # Initialize the maximum profit to 0
6 max_profit = 0
7 # Initialize the minimum price to infinity
8 min_price = float('inf')
9
10 # Loop through the prices
11 for price in prices:
12 # Update the maximum profit if the current price minus the minimum price seen so far is greater
13 max_profit = max(max_profit, price - min_price)
14 # Update the minimum price seen so far if the current price is lower
15 min_price = min(min_price, price)
16
17 # Return the maximum profit achieved
18 return max_profit
19
1class Solution {
2 public int maxProfit(int[] prices) {
3 // Initialize 'maxProfit' to 0, which is the minimum profit that can be made.
4 int maxProfit = 0;
5
6 // Assume the first price is the minimum buying price.
7 int minPrice = prices[0];
8
9 // Loop through all the prices to find the maximum profit.
10 for (int price : prices) {
11 // Calculate the maximum profit by comparing the current 'maxProfit'
12 // with the difference of the current price and the 'minPrice'.
13 maxProfit = Math.max(maxProfit, price - minPrice);
14
15 // Update the 'minPrice' if a lower price is found.
16 minPrice = Math.min(minPrice, price);
17 }
18
19 // Return the maximum profit that can be achieved.
20 return maxProfit;
21 }
22}
23
1#include <vector>
2#include <algorithm> // Include algorithm header for the min and max functions
3
4class Solution {
5public:
6 int maxProfit(vector<int>& prices) {
7 int max_profit = 0; // Variable to store the calculated maximum profit
8 int min_price = prices[0]; // Initialize the minimum price to the first price
9
10 // Loop through all the prices
11 for (int price : prices) {
12 // Update max_profit if the difference between current price and min_price is greater than current max_profit
13 max_profit = max(max_profit, price - min_price);
14
15 // Update min_price if the current price is less than the current min_price
16 min_price = min(min_price, price);
17 }
18
19 return max_profit; // Return the calculated maximum profit
20 }
21};
22
1function maxProfit(prices: number[]): number {
2 // Initialize the maximum profit as 0, since the minimum profit we can get is 0
3 let maxProfit = 0;
4 // Initialize the minimum price to the first price in the array
5 let minPrice = prices[0];
6
7 // Loop through each price in the array of prices
8 for (const price of prices) {
9 // Update maxProfit to the higher value between the existing maxProfit and
10 // the profit we get by selling at the current price minus the minPrice
11 maxProfit = Math.max(maxProfit, price - minPrice);
12 // Update minPrice to be the lower between the current minPrice and the current price
13 minPrice = Math.min(minPrice, price);
14 }
15
16 // Return the maximum profit that can be achieved
17 return maxProfit;
18}
19
Time and Space Complexity
The time complexity of the given function is O(n)
, where n
is the length of the input list prices
. This is because the function includes a single loop that iterates through each element in the list exactly once, performing a constant amount of work at each step; thus, the total work done is linear in the size of the input.
The space complexity of the function is O(1)
, indicating that the amount of additional memory used by the function does not depend on the size of the input. The function only uses a fixed number of extra variables (ans
and mi
), which require a constant amount of space regardless of the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
How many times is a tree node visited in a depth first search?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!