grid47 Exploring patterns and algorithms
Oct 25, 2024
5 min read
Solution to LeetCode 121: Best Time to Buy and Sell Stock Problem
You are given an array of prices where prices[i] represents the price of a stock on the i-th day. You want to maximize your profit by buying the stock on one day and selling it on a future day. Return the maximum profit you can achieve from this transaction. If no profit can be made, return 0.
Problem
Approach
Steps
Complexity
Input: The input consists of an array prices where prices[i] is the price of the stock on the i-th day.
Example: Input: prices = [10, 3, 15, 8, 12, 5]
Constraints:
• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4
Output: Return a single integer representing the maximum profit you can achieve from buying and selling the stock.
Example: Output: 9
Constraints:
• The profit should be the difference between the selling price and the buying price, where the selling day is after the buying day.
Goal: The goal is to maximize the profit by choosing the best day to buy and the best day to sell in the future.
Steps:
• Start by initializing the lowest price (l) as the price of the first day.
• Iterate through the prices and update the lowest price (l) as the minimum price encountered so far.
• For each price, calculate the potential profit by subtracting the lowest price (l) from the current price.
• Keep track of the maximum profit (g) encountered during the iteration.
• Return the maximum profit after processing all prices.
Goal: The problem constraints ensure that the input array will contain at least one price and that all prices will be valid within the specified range.
Steps:
• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4
Assumptions:
• The input array prices contains valid values with at least one price.
• Input: Input: prices = [10, 3, 15, 8, 12, 5]
• Explanation: The maximum profit can be achieved by buying the stock on day 2 (price = 3) and selling it on day 3 (price = 15). The profit is 15 - 3 = 12.
• Input: Input: prices = [7, 6, 4, 3, 1]
• Explanation: In this case, no profit can be made as prices keep decreasing, so the maximum profit is 0.
Approach: The problem can be solved by iterating through the prices while tracking the minimum price seen so far and calculating the potential profit for each day. The maximum profit is then updated accordingly.
Observations:
• The approach involves iterating over the array once to keep track of the minimum price and maximum profit.
• The key observation is that the best profit comes from buying at the lowest price before a higher price in the future.
Steps:
• Initialize the variable 'l' to the first price (lowest price).
• Initialize the variable 'g' to 0 (no profit initially).
• Iterate over the prices, and for each price update the lowest price (l) and calculate the profit (current price - l).
• Update the maximum profit (g) whenever a higher profit is found.
• After iterating through all prices, return the maximum profit (g).
Empty Inputs:
• There are no empty inputs allowed, as prices array has at least one element.
Large Inputs:
• The algorithm should efficiently handle inputs up to 100,000 prices.
Special Values:
• If all prices are the same or decreasing, the maximum profit will be 0.
Constraints:
• The array length will always be between 1 and 100,000, inclusive.
intmaxProfit(vector<int>& prices) {
int l = prices[0], g =0;
for(intx: prices) {
l = min(l, x);
g = max(g, x - l);
}
return g;
}
1 : Function Declaration
intmaxProfit(vector<int>& prices) {
Declare a function to compute the maximum profit from stock prices given as input.
2 : Variable Initialization
int l = prices[0], g =0;
Initialize `l` to the first price (representing the lowest price seen so far) and `g` to 0 (representing the maximum profit).
3 : Loop Iteration
for(intx: prices) {
Iterate over all stock prices to compute the lowest price and maximum profit dynamically.
4 : Minimum Update
l = min(l, x);
Update `l` to the minimum of the current price and the previously seen lowest price.
5 : Profit Update
g = max(g, x - l);
Update `g` to the maximum profit seen so far by subtracting the lowest price from the current price.
6 : Return Statement
return g;
Return the maximum profit calculated.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) because we process each element of the prices array once.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) because we only need a constant amount of space to store the variables for the minimum price and maximum profit.
