Introduction
The “Best Time to Buy and Sell Stock” is a popular coding interview question that tests your ability to find the maximum profit that can be obtained by completing at most one transaction (i.e., buy one stock and sell one stock) within a given array of stock prices. In this tutorial, we will explore different approaches to solve this problem using C++ and provide detailed explanations along with time and space complexity analyses.
Problem Statement
Given an array prices where prices[i] represents the price of a given stock on the i-th day, find the maximum profit that can be achieved. If no profit can be made, return 0.
Approach 1: Brute Force
The simplest approach to solve this problem is by using brute force. We can iterate through each possible pair of buy and sell transactions and calculate the profit for each pair. Finally, we return the maximum profit obtained.
Implementation
int maxProfit(vector<int>& prices) {
int maxProfit = 0;
int n = prices.size();
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int profit = prices[j] - prices[i];
if (profit > maxProfit) {
maxProfit = profit;
}
}
}
return maxProfit;
}Time Complexity Analysis
The time complexity for this approach is O(n^2), where n is the number of elements in the prices array. Since we have to examine each possible pair of buy and sell transactions, the number of iterations is proportional to n*(n-1)/2.
Space Complexity Analysis
The space complexity for this approach is O(1) since we only use a constant amount of additional space to store the maximum profit.
Approach 2: One Pass
We can improve the brute force approach by using a single pass through the prices array. The idea is to keep track of the minimum price encountered so far and calculate the profit if we sell the stock on the current day. We update the minimum price and maximum profit as we iterate through the array.
Implementation
int maxProfit(vector<int>& prices) {
int maxProfit = 0;
int minPrice = INT_MAX;
for (int i = 0; i < prices.size(); i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else if (prices[i] - minPrice > maxProfit) {
maxProfit = prices[i] - minPrice;
}
}
return maxProfit;
}Time Complexity Analysis
The time complexity for this approach is O(n), where n is the number of elements in the prices array. We perform a single pass through the array, visiting each element once.
Space Complexity Analysis
The space complexity for this approach is O(1) since we only use a constant amount of additional space to store the maximum profit and minimum price.
Approach 3: Dynamic Programming
We can also solve this problem using dynamic programming. We can define two state variables, buy and sell, to represent the maximum profit if we buy/sell the stock on the current day. We update these variables as we iterate through the prices array using the following recurrence relation:
buy = max(buy, -prices[i]);
sell = max(sell, buy + prices[i]);
Implementation
int maxProfit(vector<int>& prices) {
int buy = INT_MIN;
int sell = 0;
for (int i = 0; i < prices.size(); i++) {
buy = max(buy, -prices[i]);
sell = max(sell, buy + prices[i]);
}
return sell;
}Time Complexity Analysis
The time complexity for this approach is O(n), where n is the number of elements in the prices array. We perform a single pass through the array, visiting each element once.
Space Complexity Analysis
The space complexity for this approach is O(1), as we only use a constant amount of additional space to store the buy and sell variables.
Conclusion
In this tutorial, we explored three different approaches to solve the “Best Time to Buy and Sell Stock” problem using C++. We started with a brute force approach and then optimized it using a one-pass and dynamic programming approach. Each approach has its own advantages and complexities in terms of time and space requirements. It is essential to understand the problem and the characteristics of each approach to choose the most suitable one for a specific scenario.