Introduction to the Best Time to Buy and Sell Stock Problem
The "Best Time to Buy and Sell Stock" problem is one of the most iconic algorithmic challenges you will encounter in coding interviews and competitive programming. It appears frequently on platforms like LeetCode, HackerRank, and in technical interviews at major tech companies. The problem tests your ability to think about array traversal, optimization, and recognizing when a seemingly complex problem can be solved with an elegant, efficient approach.
At its core, the problem asks you to determine the maximum profit you can achieve by buying and selling a single share of stock, given a chronological list of daily prices. While a brute force solution may come to mind immediately, the real challenge lies in optimizing your solution to run efficiently, even with large datasets.
What Is the Best Time to Buy and Sell Stock Problem?
The problem statement is deceptively simple. You are given an array prices where prices[i] represents the price of a given stock on day i. You want to maximize your profit by choosing a single day to buy one share and choosing a different day in the future to sell that share. Your task is to return the maximum profit you can achieve. If no profit is possible, you return zero.
For example, consider the following input:
const prices = [7, 1, 5, 3, 6, 4];
Here, the optimal strategy is to buy on day 1 (when the price is 1) and sell on day 4 (when the price is 6), yielding a profit of 5. No other combination produces a higher profit.
Key Constraints to Understand
- You may only complete one transaction, meaning one buy followed by one sell.
- You cannot sell a stock before you buy one, so the sell day must come after the buy day.
- If prices only decrease over time, the maximum profit is zero because you would choose not to trade at all.
- The input array can be large, so time complexity matters significantly.
Why This Problem Matters
Beyond being a common interview question, this problem teaches several fundamental programming concepts. First, it demonstrates the importance of recognizing patterns in data. Second, it highlights the trade-off between time complexity and space complexity. Finally, it introduces the concept of maintaining state while iterating through a data structure, a technique you will use repeatedly in real-world applications.
In practical terms, similar logic is used in financial software for analyzing historical price data, in inventory management systems for identifying optimal purchasing windows, and in any domain where you need to find the maximum difference between two values in a sequence with ordering constraints.
The Brute Force Approach
The most intuitive solution is to compare every possible pair of buy and sell days. For each day, you consider buying at that price and then check every subsequent day as a potential sell day. You track the maximum profit found across all combinations.
function maxProfitBruteForce(prices) {
let maxProfit = 0;
for (let i = 0; i < prices.length; i++) {
for (let j = i + 1; j < prices.length; j++) {
const profit = prices[j] - prices[i];
if (profit > maxProfit) {
maxProfit = profit;
}
}
}
return maxProfit;
}
console.log(maxProfitBruteForce([7, 1, 5, 3, 6, 4])); // Output: 5
console.log(maxProfitBruteForce([7, 6, 4, 3, 1])); // Output: 0
While this solution works correctly, it has a time complexity of O(nĀ²) because of the nested loops. For small arrays, this is fine, but when the input grows to tens of thousands of prices, the performance degrades rapidly. This is where optimization becomes essential.
The Optimized One-Pass Solution
The key insight for optimization is that you only need to traverse the array once. As you iterate through the prices, you keep track of the minimum price you have seen so far. At each step, you calculate the potential profit if you were to sell at the current price, having bought at that minimum price. You update the maximum profit whenever you find a better one.
This approach works because the minimum price seen so far always represents the best possible buying opportunity up to the current day. Any future selling price compared against this minimum gives you the best possible profit at that point in time.
function maxProfit(prices) {
let minPrice = Infinity;
let maxProfit = 0;
for (let i = 0; i < prices.length; i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else {
const potentialProfit = prices[i] - minPrice;
if (potentialProfit > maxProfit) {
maxProfit = potentialProfit;
}
}
}
return maxProfit;
}
console.log(maxProfit([7, 1, 5, 3, 6, 4])); // Output: 5
console.log(maxProfit([7, 6, 4, 3, 1])); // Output: 0
console.log(maxProfit([2, 4, 1])); // Output: 2
This solution runs in O(n) time complexity because it only passes through the array once. The space complexity is O(1) since it uses only two variables regardless of the input size. This is a dramatic improvement over the brute force approach.
Breaking Down the Logic Step by Step
Let us trace through the example [7, 1, 5, 3, 6, 4] to understand exactly how the algorithm works:
- Day 0: Price is 7. Since 7 is less than Infinity, set minPrice to 7. maxProfit remains 0.
- Day 1: Price is 1. Since 1 is less than 7, set minPrice to 1. maxProfit remains 0.
- Day 2: Price is 5. Since 5 is not less than 1, calculate potential profit: 5 - 1 = 4. Set maxProfit to 4.
- Day 3: Price is 3. Calculate potential profit: 3 - 1 = 2. maxProfit stays at 4.
- Day 4: Price is 6. Calculate potential profit: 6 - 1 = 5. Set maxProfit to 5.
- Day 5: Price is 4. Calculate potential profit: 4 - 1 = 3. maxProfit stays at 5.
The final answer is 5, which matches our expected output.
Handling Edge Cases
A robust solution must account for edge cases that could cause unexpected behavior. Let us examine some scenarios and how our function handles them.
function maxProfit(prices) {
// Handle empty or single-element arrays
if (!prices || prices.length < 2) {
return 0;
}
let minPrice = Infinity;
let maxProfit = 0;
for (let i = 0; i < prices.length; i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else {
const potentialProfit = prices[i] - minPrice;
if (potentialProfit > maxProfit) {
maxProfit = potentialProfit;
}
}
}
return maxProfit;
}
console.log(maxProfit([])); // Output: 0
console.log(maxProfit([5])); // Output: 0
console.log(maxProfit([5, 5, 5])); // Output: 0
console.log(maxProfit([1, 2])); // Output: 1
console.log(maxProfit([2, 1])); // Output: 0
Adding the guard clause at the beginning ensures the function does not attempt to process invalid input. When the array has fewer than two elements, no transaction is possible, so returning zero is the correct behavior.
Using a For-Of Loop for Cleaner Code
JavaScript offers several ways to iterate over arrays. Using a for...of loop can make the code more readable, especially when you do not need the index. Here is the same algorithm written with this modern syntax:
function maxProfit(prices) {
if (!prices || prices.length < 2) {
return 0;
}
let minPrice = Infinity;
let maxProfit = 0;
for (const price of prices) {
minPrice = Math.min(minPrice, price);
maxProfit = Math.max(maxProfit, price - minPrice);
}
return maxProfit;
}
console.log(maxProfit([7, 1, 5, 3, 6, 4])); // Output: 5
This version leverages Math.min and Math.max to simplify the comparison logic. The result is functionally identical but more concise. Some developers prefer this style because it clearly expresses the intent of updating the minimum price and maximum profit at each step.
Tracking the Buy and Sell Days
In some variations of the problem, you may need to return not just the maximum profit but also the specific days on which you should buy and sell. This requires tracking additional state during the iteration.
function maxProfitWithDays(prices) {
if (!prices || prices.length < 2) {
return { profit: 0, buyDay: -1, sellDay: -1 };
}
let minPrice = Infinity;
let minPriceDay = -1;
let maxProfit = 0;
let buyDay = -1;
let sellDay = -1;
for (let i = 0; i < prices.length; i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
minPriceDay = i;
} else {
const potentialProfit = prices[i] - minPrice;
if (potentialProfit > maxProfit) {
maxProfit = potentialProfit;
buyDay = minPriceDay;
sellDay = i;
}
}
}
return { profit: maxProfit, buyDay, sellDay };
}
const result = maxProfitWithDays([7, 1, 5, 3, 6, 4]);
console.log(result);
// Output: { profit: 5, buyDay: 1, sellDay: 4 }
Notice that we update buyDay and sellDay only when we find a new maximum profit. This ensures the returned days correspond to the optimal transaction. The minPriceDay variable tracks the day of the current minimum price, which becomes the buy day whenever a new maximum profit is discovered.
Best Practices for Solving This Problem
When approaching this problem, whether in an interview or in production code, keep the following best practices in mind:
- Start with the brute force solution. It helps you understand the problem fully and gives you a baseline to optimize from. Interviewers often want to see your thought process before you jump to the optimal solution.
- Identify the invariant. In this case, the invariant is the minimum price seen so far. Recognizing invariants is a skill that transfers to many other algorithmic problems.
- Handle edge cases explicitly. Empty arrays, single-element arrays, and strictly decreasing arrays should all be considered. Defensive programming prevents bugs in production.
- Choose descriptive variable names. Names like
minPriceandmaxProfitmake the code self-documenting. Avoid generic names likeaortempin any code that others might read. - Test with multiple inputs. Verify your solution with increasing arrays, decreasing arrays, arrays with duplicate values, and arrays where the maximum profit occurs at various positions.
- Understand the time and space complexity. Being able to articulate why your solution is O(n) time and O(1) space demonstrates a deep understanding of algorithmic efficiency.
Common Mistakes to Avoid
Even experienced developers can make errors when solving this problem. One common mistake is initializing minPrice to prices[0] without first checking if the array is empty. This leads to undefined behavior when the input is invalid. Always validate your input before accessing elements.
Another frequent error is updating the maximum profit before updating the minimum price within the same iteration. This can cause the algorithm to consider buying and selling on the same day, which violates the problem constraints. The order of operations in the loop matters.
// Incorrect: updates maxProfit before minPrice, causing same-day transactions
function maxProfitIncorrect(prices) {
let minPrice = Infinity;
let maxProfit = 0;
for (const price of prices) {
maxProfit = Math.max(maxProfit, price - minPrice);
minPrice = Math.min(minPrice, price);
}
return maxProfit;
}
// This actually works because Math.max with Infinity yields a negative number,
// but the logic is fragile and confusing. Prefer the explicit if-else structure.
While the above code technically produces correct results due to how Infinity behaves in arithmetic, the logic is less clear and can lead to subtle bugs when modified. Prefer the explicit structure that separates the two concerns.
Extending to Multiple Transactions
A natural extension of this problem allows multiple buy-sell transactions. While the single-transaction version is the foundation, understanding how to extend it broadens your problem-solving toolkit. Here is a brief example where you can buy and sell as many times as you want, but you can only hold one share at a time:
function maxProfitMultipleTransactions(prices) {
let totalProfit = 0;
for (let i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
totalProfit += prices[i] - prices[i - 1];
}
}
return totalProfit;
}
console.log(maxProfitMultipleTransactions([7, 1, 5, 3, 6, 4])); // Output: 7
// Buy at 1, sell at 5 (profit 4), buy at 3, sell at 6 (profit 3). Total: 7.
This greedy approach captures every upward price movement as a profit opportunity. It is a different problem with a different solution strategy, but it builds on the same foundation of array traversal and profit calculation.
Conclusion
The Best Time to Buy and Sell Stock problem is a perfect example of how a seemingly complex challenge can be reduced to an elegant, efficient solution through careful analysis. By moving from a brute force O(nĀ²) approach to a single-pass O(n) algorithm, you demonstrate not only coding ability but also algorithmic thinking. The key takeaway is the technique of maintaining running state, such as the minimum price seen so far, while iterating through data. This pattern appears across countless problems in software development, from financial analysis to data processing pipelines. Master this problem, and you will be well-equipped to tackle a wide range of array-based algorithmic challenges in JavaScript and beyond.