Stock Buy and Sell

Problem Overview
The problem is a classic question in stock trading optimizations, titled "Best Time to Buy and Sell Stock." It is categorized under the topic of Arrays on LeetCode. The task is to determine the maximum profit achievable from a given array representing the daily price of a stock. You are only allowed to make one purchase and one sale.
LeetCode URL: Best Time to Buy and Sell Stock
The problem requires you to optimize your trading strategy to maximize profit and considers real-world constraints like buying the stock before selling it.
Understanding the Problem
Given an array prices
where prices[i]
is the price of a stock on the i
th day, you need to compute the maximum profit you can achieve by completing exactly one purchase followed by one sale. If no profit can be made, return 0.
Example
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.
This example clarifies that you must look for the lowest price to buy and the highest subsequent price to sell for the maximum profit.
Key DSA Concepts and Theory
Arrays
Arrays are a basic data structure where you'll store the daily prices of the stock. They allow efficient access and iteration over elements, which is essential for comparing and computing potential profits on different days.
Single Pass Algorithm
A single pass algorithm involves going through the array once to solve the problem. It is optimal for problems needing linear time solutions, as double iteration (nested loops) would increase time complexity significantly.
Dynamic Programming Approach
A useful approach here is using a dynamic programming-like technique, maintaining the minimum price observed so far and calculating the potential profit at every step.
Solution Approach
Step-by-Step Solution
To solve this problem, we can loop through the given array, keeping track of the lowest price encountered so far and computing the potential profit at each step. Here’s how you can achieve this:
Initialize Variables:
- Create a variable
min_price
and set it to a large value (infinity). - Create a variable
max_profit
and set it to 0.
- Create a variable
Iterate through the Array:
- For each price in the array:
- Update
min_price
to be the minimum ofmin_price
and the current price. - Calculate the profit if you sell at the current price:
current_profit = price - min_price
. - Update
max_profit
to be the maximum of itself andcurrent_profit
.
- Update
- For each price in the array:
Return the Result:
- After completing the loop,
max_profit
holds the maximum profit possible.
- After completing the loop,
C++ Code Implementation
#include <vector>
#include <algorithm>
#include <limits.h>
class Solution {
public:
int maxProfit(std::vector<int>& prices) {
int min_price = INT_MAX;
int max_profit = 0;
for (int price : prices) {
min_price = std::min(min_price, price);
int current_profit = price - min_price;
max_profit = std::max(max_profit, current_profit);
}
return max_profit;
}
};
Java Code Implementation
class Solution {
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int price : prices) {
if (price < minPrice) {
minPrice = price;
} else if (price - minPrice > maxProfit) {
maxProfit = price - minPrice;
}
}
return maxProfit;
}
}
Time and Space Complexity Analysis
Time Complexity:
- The solution runs in O(n) time, where n is the number of days (length of the
prices
array). This is because we iterate through the array once.
Space Complexity:
- The space complexity is O(1), as no additional space proportional to input size is required; only a few variables are used for tracking the calculations.
Common Mistakes to Avoid
- Ignoring Negative Profits: Make sure to handle cases where buying a stock after selling results in a negative profit. By initializing
max_profit
to 0, you ensure that if no profit is possible, the function returns 0. - Incorrect Tracking of Minimum Price: Updating
min_price
should always reflect the lowest value encountered up to the current day.
Similar Problems on LeetCode
- Best Time to Buy and Sell Stock II (LeetCode 122)
- Best Time to Buy and Sell Stock III (LeetCode 123)
- Best Time to Buy and Sell Stock with Cooldown (LeetCode 309)
- Maximum Subarray (LeetCode 53)
Additional Resources and References
This article should provide you with a comprehensive understanding of how to tackle the "Best Time to Buy and Sell Stock" problem on LeetCode using efficient algorithms and concepts.