Best Time to Buy and Sell Stock Solution Explained – Step-by-Step

Algorithms / Two Pointers

Best Time to Buy and Sell Stock

Easy

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 and a different day in the future to sell. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, 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.

Explanation

The key insight to solve this problem efficiently is that for each day, we need to know the minimum price seen so far. The maximum profit achievable by selling on the current day is simply the current price minus the minimum price we've seen before this day.

We use a two pointers approach where we track:

min_price - the minimum price seen so far (potential buy day)
max_profit - the maximum profit achievable so far

For each price in the array, we:

Calculate potential profit: current_price - min_price
Update max_profit if this profit is larger
Update min_price if current price is smaller

This approach works because we must buy before we sell. By always tracking the minimum price seen so far, we ensure that for any selling day, we know the best possible buying day before it.

Idea Map

Start

Initialize min_price = ∞, max_profit = 0

For each price in prices

1. profit = price - min_price
2. If profit > max_profit
Update max_profit = profit
3. If price < min_price
Update min_price = price

Return max_profit

Complexity Analysis

Time Complexity

O(n) - We traverse the array exactly once, performing constant-time operations at each element.

Space Complexity

O(1) - We only use two variables regardless of input size.

Code


def maxProfit(prices):
Initializes the function `maxProfit` which takes the array `prices` as input.
    min_price = float('inf')
Sets the minimum price to infinity, ensuring the first price will always be lower.
    max_profit = 0
Initializes maximum profit to 0, representing no profit if prices only decrease.
    for price in prices:
Loops through each price in the prices array.
        profit = price - min_price
Calculates profit if we sold at current price after buying at the minimum price seen so far.
        max_profit = max(max_profit, profit)
Updates max_profit if the current profit is greater than the previous maximum.
        min_price = min(min_price, price)
Updates min_price if the current price is lower than any we've seen before.
    return max_profit
Returns the maximum profit achievable (0 if no profit is possible).


public int maxProfit(int[] prices) {
Initializes the function `maxProfit` which takes the array `prices` as input.
    int minPrice = Integer.MAX_VALUE;
Sets the minimum price to the maximum integer value, ensuring the first price will always be lower.
    int maxProfit = 0;
Initializes maximum profit to 0, representing no profit if prices only decrease.
    for (int price : prices) {
Loops through each price in the prices array using enhanced for loop.
        int profit = price - minPrice;
Calculates profit if we sold at current price after buying at the minimum price seen so far.
        maxProfit = Math.max(maxProfit, profit);
Updates maxProfit if the current profit is greater than the previous maximum.
        minPrice = Math.min(minPrice, price);
Updates minPrice if the current price is lower than any we've seen before.
    }
End of the for loop.
    return maxProfit;
Returns the maximum profit achievable (0 if no profit is possible).
}
End of the function.


int maxProfit(vector<int>& prices) {
Initializes the function `maxProfit` which takes a reference to the vector `prices` as input.
    int minPrice = INT_MAX;
Sets the minimum price to the maximum integer value, ensuring the first price will always be lower.
    int maxProfit = 0;
Initializes maximum profit to 0, representing no profit if prices only decrease.
    for (int price : prices) {
Loops through each price in the prices vector using range-based for loop.
        int profit = price - minPrice;
Calculates profit if we sold at current price after buying at the minimum price seen so far.
        maxProfit = max(maxProfit, profit);
Updates maxProfit if the current profit is greater than the previous maximum.
        minPrice = min(minPrice, price);
Updates minPrice if the current price is lower than any we've seen before.
    }
End of the for loop.
    return maxProfit;
Returns the maximum profit achievable (0 if no profit is possible).
}
End of the function.

Edge Cases & Common Mistakes

⚠️

Selling before buying

Always update the minimum price after calculating profit. This ensures we always buy before we sell.

💡

Decreasing prices

If prices only decrease, return 0. The algorithm handles this correctly because max_profit starts at 0 and never becomes negative.

✓

Single day prices

The algorithm correctly returns 0 for arrays with less than 2 elements since you can't complete a transaction.

What is the Two Pointers Technique?

The two pointers technique is a pattern where two pointers iterate through the array simultaneously. One pointer typically leads the other, and we process elements between them. It's commonly used for searching pairs in sorted arrays, optimizing subarrays, and solving problems with sequential dependencies.

Learn more about two pointers →

lightbulb

Disclaimer: This problem is for educational purposes. Practice the 'Best Time to Buy and Sell Stock' problem on LeetCode.

AlgoExplained.dev