Best Time to Buy and Sell Stock
In this blog, we will discuss the "Best Time to Buy and Sell Stock" problem, which is a popular problem in coding interviews. We will go through the problem statement, explain the approach, and provide both brute force and optimal solutions. Additionally, we will perform a dry run of the code for better understanding and analyze the time and space complexity of each solution.
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.
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.Practice: Leetcode Link
Brute Force Solution
The brute force approach involves checking every possible pair of buy and sell days to find the maximum profit. This method is straightforward but inefficient due to its O(n2) time complexity.
Space Complexity: O(1) as we are not using any extra space except for variables.
Algorithm
1. Initialize a variable `maxProfit` to 0.
2. Use two nested loops to traverse all pairs of days (i, j) where i < j.
3. For each pair, calculate the profit: profit = prices[j] - prices[i].
4. If the profit is greater than `maxProfit`, update `maxProfit`.
5. Return `maxProfit`.
Java Code
package codeKatha;
public class StockProfit {
public int maxProfitBruteForce(int[] prices) {
int maxProfit = 0;
for (int i = 0; i < prices.length; i++) {
for (int j = i + 1; j < prices.length; j++) {
int profit = prices[j] - prices[i];
if (profit > maxProfit) {
maxProfit = profit;
}
}
}
return maxProfit;
}
}
Dry Run for Brute Force Solution
Consider the input array [7, 1, 5, 3, 6, 4] with the target of maximizing profit:
Step-by-step Execution: 1. Initialize maxProfit = 0. 2. i = 0: - j = 1: prices[1] - prices[0] = 1 - 7 = -6 (maxProfit remains 0) - j = 2: prices[2] - prices[0] = 5 - 7 = -2 (maxProfit remains 0) - j = 3: prices[3] - prices[0] = 3 - 7 = -4 (maxProfit remains 0) - j = 4: prices[4] - prices[0] = 6 - 7 = -1 (maxProfit remains 0) - j = 5: prices[5] - prices[0] = 4 - 7 = -3 (maxProfit remains 0) 3. i = 1: - j = 2: prices[2] - prices[1] = 5 - 1 = 4 (maxProfit updated to 4) - j = 3: prices[3] - prices[1] = 3 - 1 = 2 (maxProfit remains 4) - j = 4: prices[4] - prices[1] = 6 - 1 = 5 (maxProfit updated to 5) - j = 5: prices[5] - prices[1] = 4 - 1 = 3 (maxProfit remains 5) 4. Continue similarly for i = 2, 3, 4. 5. Final maxProfit is 5.
Explanation:
We compare every possible pair of buying and selling days. The maximum profit is found by buying on day 2 (price 1) and selling on day 5 (price 6), resulting in a profit of 5.
Time and Space Complexity for Brute Force Solution
Time Complexity: O(n2) because of the two nested loops. Space Complexity: O(1) since we are not using any additional space.
Optimal Solution Using Single Pass
The optimal solution involves a single pass through the array while keeping track of the minimum price seen so far and calculating the maximum profit based on the difference between the current price and the minimum price. This method has a time complexity of O(n).
Space Complexity: O(1) as we are not using any extra space except for variables.
Algorithm
1. Initialize two variables: `minPrice` to Integer.MAX_VALUE and `maxProfit` to 0.
2. Loop through the array.
3. For each price, update `minPrice` to be the minimum of `minPrice` and the current price.
4. Calculate the profit: profit = current price - minPrice.
5. Update `maxProfit` to be the maximum of `maxProfit` and profit.
6. Return `maxProfit`.
Java Code
package codeKatha;
public class StockProfit {
public int maxProfitOptimal(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else if (prices[i] - minPrice > maxProfit) {
maxProfit = prices[i] - minPrice;
}
}
return maxProfit;
}
}
Dry Run for Optimal Solution
Consider the input array [7, 1, 5, 3, 6, 4] with the target of maximizing profit:
Step-by-step Execution: 1. Initialize minPrice = Integer.MAX_VALUE, maxProfit = 0. 2. i = 0: - prices[0] = 7 - minPrice updated to 7 (minPrice = 7) - No profit calculation (since it's the first element) 3. i = 1: - prices[1] = 1 - minPrice updated to 1 (minPrice = 1) - No profit calculation (since minPrice just updated) 4. i = 2: - prices[2] = 5 - Calculate profit: 5 - 1 = 4 - maxProfit updated to 4 (maxProfit = 4) 5. i = 3: - prices[3] = 3 - Calculate profit: 3 - 1 = 2 - maxProfit remains 4 6. i = 4: - prices[4] = 6 - Calculate profit: 6 - 1 = 5 - maxProfit updated to 5 (maxProfit = 5) 7. i = 5: - prices[5] = 4 - Calculate profit: 4 - 1 = 3 - maxProfit remains 5 8. Final maxProfit is 5.
Explanation:
We traverse the array while keeping track of the minimum price seen so far and calculating the potential profit at each step. The maximum profit is found by buying on day 2 (price 1) and selling on day 5 (price 6), resulting in a profit of 5.
Time and Space Complexity for Optimal Solution
Time Complexity: O(n) because we traverse the array once. Space Complexity: O(1) since we are using only a constant amount of extra space.
Edge Cases
- If the array contains only one element, return 0 as no transaction can be made.
- If the prices are in descending order, return 0 as no profit can be made.
- If all prices are the same, return 0 as no profit can be made.
Example Edge Cases:
Input: prices = [1] Output: 0 Input: prices = [5, 4, 3, 2, 1] Output: 0 Input: prices = [2, 2, 2, 2, 2] Output: 0
With this explanation, we have covered both brute force and optimal solutions to the Best Time to Buy and Sell Stock problem. The brute force method is simple but inefficient, while the single-pass approach using a minimum price tracker provides a much more efficient solution. Understanding both methods helps in grasping fundamental concepts of problem-solving and algorithm optimization.
Comments
Post a Comment