Solving Best Time to Buy and Sell Stock in Python: Step-by-Step Guide

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 on platforms like LeetCode, in coding interviews, and in computer science coursework. At its core, the problem asks you to determine the maximum profit you can achieve by buying and selling a single share of a stock, given a list of daily prices. While the premise sounds simple, the problem elegantly tests your understanding of array traversal, optimization, and time complexity analysis.

In this tutorial, you will learn what the problem is, why it matters in real-world software engineering, how to solve it using multiple approaches in Python, and the best practices you should follow when writing similar algorithmic code. By the end, you will be able to implement an optimal O(n) solution confidently and explain the reasoning behind it.

What Is the Best Time to Buy and Sell Stock Problem?

The classic version of the problem (LeetCode 121) is stated as follows: 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 one share and choosing a different day in the future to sell that share. Return the maximum profit you can achieve from this transaction. If no profit is possible, return 0.

For example, given the input [7, 1, 5, 3, 6, 4], the optimal strategy is to buy on day 2 (price = 1) and sell on day 5 (price = 6), yielding a profit of 5. Given [7, 6, 4, 3, 1], prices only decline, so no profitable transaction is possible and the answer is 0.

Key Constraints to Understand

You may only complete at most one transaction (one buy and one sell).
You must buy before you sell; you cannot sell first.
You cannot hold multiple shares simultaneously.
If no profit is achievable, the result must be 0, not a negative number.

Why This Problem Matters

Beyond its popularity in interviews, this problem teaches several foundational concepts that every developer should master. First, it demonstrates the power of a single-pass algorithm: a naive solution might compare every pair of days, but an optimal solution processes the array in linear time. This kind of optimization thinking is essential when working with large datasets in production systems.

Second, the problem introduces the concept of tracking state as you iterate. You maintain the minimum price seen so far and the maximum profit achievable at each step. This pattern — keeping running aggregates while traversing data — appears constantly in real-world applications such as stream processing, financial analytics, and monitoring dashboards.

Finally, the problem is a gateway to a whole family of related stock trading problems, including variants that allow multiple transactions, transaction fees, cooldown periods, and short selling. Mastering the basic version prepares you to tackle these more complex dynamic programming challenges.

Approach 1: Brute Force Solution

The most intuitive solution is to consider every possible pair of buy and sell days. For each day i, try selling on every subsequent day j, compute the profit, and track the maximum. While correct, this approach has a time complexity of O(n²), which becomes impractical for large inputs.

def max_profit_brute_force(prices):
    max_profit = 0
    n = len(prices)
    for i in range(n):
        for j in range(i + 1, n):
            profit = prices[j] - prices[i]
            if profit > max_profit:
                max_profit = profit
    return max_profit

# Example usage
prices = [7, 1, 5, 3, 6, 4]
print(max_profit_brute_force(prices))  # Output: 5

This solution works for small arrays, but if prices contains tens of thousands of entries, the nested loops will cause noticeable slowdowns. Interviewers will almost always ask you to improve upon this.

Approach 2: Single-Pass Optimal Solution

The optimal solution uses a single pass through the array while maintaining two variables: the minimum price encountered so far and the maximum profit achievable. As you iterate, you update the minimum price if the current price is lower, otherwise you calculate the potential profit from selling at the current price and update the maximum profit if this potential is greater.

This approach runs in O(n) time and uses O(1) extra space, making it highly efficient and suitable for production use.

def max_profit(prices):
    min_price = float('inf')
    max_profit = 0

    for price in prices:
        if price < min_price:
            min_price = price
        else:
            profit = price - min_price
            if profit > max_profit:
                max_profit = profit

    return max_profit

# Example usage
prices = [7, 1, 5, 3, 6, 4]
print(max_profit(prices))  # Output: 5

prices = [7, 6, 4, 3, 1]
print(max_profit(prices))  # Output: 0

How the Algorithm Works Step by Step

Let us trace through the input [7, 1, 5, 3, 6, 4] to understand the logic:

Initialize min_price to infinity and max_profit to 0.
Day 1, price = 7: 7 is less than infinity, so min_price becomes 7.
Day 2, price = 1: 1 is less than 7, so min_price becomes 1.
Day 3, price = 5: 5 is not less than 1, so profit = 5 - 1 = 4. max_profit becomes 4.
Day 4, price = 3: profit = 3 - 1 = 2. max_profit stays 4.
Day 5, price = 6: profit = 6 - 1 = 5. max_profit becomes 5.
Day 6, price = 4: profit = 4 - 1 = 3. max_profit stays 5.
Final answer: 5.

The key insight is that by the time you reach a selling day, you already know the lowest buying price that came before it. This eliminates the need for nested loops.

Approach 3: Using Python's Built-in Functions

For a more Pythonic flavor, you can leverage the itertools.accumulate function to track the running minimum and compute profits in a functional style. This approach is elegant but slightly less readable for beginners.

from itertools import accumulate

def max_profit_functional(prices):
    if not prices:
        return 0
    running_min = accumulate(prices, min)
    return max((p - m for p, m in zip(prices, running_min)), default=0)

# Example usage
prices = [7, 1, 5, 3, 6, 4]
print(max_profit_functional(prices))  # Output: 5

This version is concise and demonstrates Python's expressive power, but in performance-critical code, the explicit loop in Approach 2 is generally preferred because it avoids the overhead of generator expressions and function calls.

Handling Edge Cases

Robust code must handle edge cases gracefully. Consider the following scenarios:

An empty list of prices.
A list with only one price (cannot complete a transaction).
A strictly decreasing list (no profit possible).
A strictly increasing list (buy on first day, sell on last).
A list where all prices are identical (profit is 0).

def max_profit_robust(prices):
    if not prices or len(prices) < 2:
        return 0

    min_price = float('inf')
    max_profit = 0

    for price in prices:
        if price < min_price:
            min_price = price
        elif price - min_price > max_profit:
            max_profit = price - min_price

    return max_profit

# Edge case tests
print(max_profit_robust([]))            # Output: 0
print(max_profit_robust([5]))           # Output: 0
print(max_profit_robust([5, 4, 3, 2]))  # Output: 0
print(max_profit_robust([1, 2, 3, 4]))  # Output: 3
print(max_profit_robust([3, 3, 3, 3]))  # Output: 0

Best Practices for Solving This Problem

Always Analyze Time and Space Complexity

Before finalizing any solution, state its time and space complexity explicitly. The optimal solution runs in O(n) time because it visits each element once, and it uses O(1) space because it only stores two variables regardless of input size. Being able to articulate this clearly is crucial in interviews and code reviews.

Prefer Readable Variable Names

Use descriptive names like min_price and max_profit rather than single letters like m and p. Readable code reduces bugs and makes maintenance easier, especially when the logic is subtle.

Validate Inputs Early

Check for empty or insufficient input at the beginning of your function. Failing fast prevents confusing errors later and makes your function's contract explicit to other developers.

Write Test Cases

Always test your solution against a variety of inputs, including edge cases. A simple test suite ensures your code remains correct as it evolves. Consider using a framework like pytest for larger projects.

def test_max_profit():
    assert max_profit_robust([7, 1, 5, 3, 6, 4]) == 5
    assert max_profit_robust([7, 6, 4, 3, 1]) == 0
    assert max_profit_robust([]) == 0
    assert max_profit_robust([5]) == 0
    assert max_profit_robust([1, 2, 3, 4, 5]) == 4
    assert max_profit_robust([2, 4, 1]) == 2
    print("All tests passed.")

test_max_profit()

Consider the Related Variants

Once you are comfortable with the basic problem, explore its variants. For example, "Best Time to Buy and Sell Stock II" allows multiple transactions, "Best Time to Buy and Sell Stock with Cooldown" adds a waiting period between transactions, and "Best Time to Buy and Sell Stock with Transaction Fee" introduces a cost per trade. These variants typically require dynamic programming and build directly upon the intuition you developed here.

Conclusion

The Best Time to Buy and Sell Stock problem is a deceptively simple challenge that rewards careful thinking about array traversal and state tracking. By starting with a brute force solution and refining it into a single-pass O(n) algorithm, you develop the kind of optimization mindset that distinguishes strong developers. Remember to handle edge cases, write clear tests, and always communicate the complexity of your code. With these practices in place, you will be well prepared not only for this problem but for the entire family of stock trading challenges and the broader category of array-based optimization problems.