Introduction
The “Best Time to Buy and Sell Stock” problem is a popular coding interview question that tests your ability to find the maximum profit that can be obtained by buying and selling a stock on given days.
In this tutorial, we will explore various approaches to solve this problem in Java. We will provide step-by-step explanations and analyze the time and space complexities of each approach.
The Problem
Given an array of stock prices, where the values represent the prices of a stock on different days, we need to determine the maximum profit that can be obtained by buying and selling the stock.
The constraint is that we can only make one transaction, i.e., buy one stock and sell one stock.
Solution 1: Brute Force
The simplest approach to solving this problem is by using brute force. We can loop through every possible pair of buying and selling days and calculate the profit. Finally, we return the maximum profit obtained.
Let’s implement this approach:
public class StockProfitCalculator {
public static int maxProfit(int[] prices) {
int maxProfit = 0;
for (int i = 0; i < prices.length - 1; i++) {
for (int j = i + 1; j < prices.length; j++) {
int profit = prices[j] - prices[i];
if (profit > maxProfit) {
maxProfit = profit;
}
}
}
return maxProfit;
}
}Time Complexity
The double nested loop iterates through all possible pairs of buying and selling days, resulting in a time complexity of O(n^2), where n is the length of the input array.
Space Complexity
This solution only uses a constant amount of additional space, so the space complexity is O(1).
Solution 2: One Pass
Although the brute force solution is correct, it is highly inefficient for larger inputs. We can optimize the solution by performing only a single pass through the array and keeping track of the minimum price and maximum profit found so far.
Let’s implement this approach:
public class StockProfitCalculator {
public static int maxProfit(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;
}
}Time Complexity
This solution performs a single pass through the array, resulting in a time complexity of O(n), where n is the length of the input array.
Space Complexity
This solution only uses a constant amount of additional space, so the space complexity is O(1).
Solution 3: Dynamic Programming
Another approach to solve this problem is by using dynamic programming. We can create an array to store the maximum profit we can obtain at each day, considering all previous days.
Let’s implement this approach:
public class StockProfitCalculator {
public static int maxProfit(int[] prices) {
int[] dp = new int[prices.length];
dp[0] = 0;
int minPrice = prices[0];
for (int i = 1; i < prices.length; i++) {
dp[i] = Math.max(dp[i-1], prices[i] - minPrice);
minPrice = Math.min(minPrice, prices[i]);
}
return dp[prices.length - 1];
}
}Time Complexity
This solution performs a single pass through the array, resulting in a time complexity of O(n), where n is the length of the input array.
Space Complexity
This solution uses an additional array of the same length as the input array, resulting in a space complexity of O(n).
Solution 4: Peak and Valley
The "Peak and Valley" approach is another way to solve this problem efficiently. The idea is to find consecutive peaks and valleys in the array and calculate the difference between each pair. Then, we sum all positive differences to obtain the maximum profit.
Let's implement this approach:
public class StockProfitCalculator {
public static int maxProfit(int[] prices) {
int i = 0;
int valley = prices[0];
int peak = prices[0];
int maxProfit = 0;
while (i < prices.length - 1) {
while (i < prices.length - 1 && prices[i] >= prices[i+1]) {
i++;
}
valley = prices[i];
while (i < prices.length - 1 && prices[i] <= prices[i+1]) {
i++;
}
peak = prices[i];
maxProfit += peak - valley;
}
return maxProfit;
}
}Time Complexity
This solution performs a single pass through the array, resulting in a time complexity of O(n), where n is the length of the input array.
Space Complexity
This solution only uses a constant amount of additional space, so the space complexity is O(1).
Conclusion
In this tutorial, we explored multiple approaches to solve the "Best Time to Buy and Sell Stock" problem in Java. We discussed the brute force approach, the one-pass approach, the dynamic programming approach, and the peak and valley approach. We provided step-by-step explanations, time and space complexity analyses for each approach, and implemented the solutions accordingly.
Remember to analyze the constraints of the problem and optimize your solution accordingly to improve its efficiency. Understanding and practicing these types of interview questions will enhance your problem-solving skills, making you better prepared for future coding challenges and job interviews.