Leetcode – Best Time to Buy and Sell Stock in Python

Spread the love

Introduction

The Best Time to Buy and Sell Stock problem is a classic and popular problem in LeetCode. It’s a wonderful introductory problem for learning about dynamic programming and array manipulation. The problem combines elements of both finance and algorithms and is a good simulation of real-world scenarios. In this article, we’ll dissect the problem, understand the intricacies involved, and explore multiple Python solutions, each with varying time complexity and space optimization.

Understanding the Problem

The problem statement is quite simple: You are given an array of prices where prices[i] is the price of a given stock on the ith day. You are only permitted to complete one transaction, which means you can buy one and sell one share of the stock. The task is to find the maximum profit you can achieve from this transaction. If you cannot make any profit, return 0.

For example, given prices = [7, 1, 5, 3, 6, 4], the maximum profit you can achieve is 5 (buy on day 2 for 1 and sell on day 5 for 6).

Approach 1: Brute Force

The most basic approach is to consider every possible pair of days. Calculate the difference between the prices for each pair, and keep track of the maximum difference (profit).

Here’s the Python code for the brute force approach:

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

This brute force approach has a time complexity of O(N^2), and may not be efficient for large input arrays.

Approach 2: One-pass Solution

We can greatly optimize the brute force approach by keeping track of the minimum price as we iterate through the array and calculating the profit for each day assuming we sell on that day. This allows us to determine the maximum profit in a single pass through the array.

Here’s the Python code for the optimized one-pass approach:

def max_profit(prices):
    max_profit = 0
    min_price = float("inf")
    
    for price in prices:
        if price < min_price:
            min_price = price
        else:
            max_profit = max(max_profit, price - min_price)
    
    return max_profit

This approach has a time complexity of O(N), which is much more efficient than the brute force method.

Approach 3: Dynamic Programming

While the one-pass solution is already quite efficient, dynamic programming can offer an alternative view of the problem. By maintaining two arrays – one for the maximum profit and one for the minimum price up to that point, we can achieve a similar one-pass effect with dynamic programming.

Here’s the Python code for the dynamic programming approach:

def max_profit(prices):
    if not prices:
        return 0
    
    n = len(prices)
    max_profit = [0] * n
    min_price = [0] * n
    min_price[0] = prices[0]
    
    for i in range(1, n):
        min_price[i] = min(min_price[i-1], prices[i])
        max_profit[i] = max(max_profit[i-1], prices[i] - min_price[i-1])
    
    return max_profit[-1]

This dynamic programming approach also has a time complexity of O(N) but uses O(N) additional space for the arrays.

Key Insights and Tips

  1. Understanding the requirements of the problem and restrictions is crucial. For example, the order of buying and selling is important, and this insight leads to the optimized one-pass solution.
  2. Always think of whether a brute force solution can be optimized by keeping track of relevant information during the traversal.
  3. Dynamic programming is a powerful technique, but sometimes, as in this case, simpler solutions can achieve the same efficiency with less space complexity.

Conclusion

The Best Time to Buy and Sell Stock problem is a classic example of how an understanding of problem constraints and efficient traversal techniques can convert a brute force solution into an efficient algorithm. The various approaches we explored – brute force, one-pass, and dynamic programming – offer different perspectives on how the problem can be tackled. This problem serves as a stepping stone for more complex variations, such as being allowed to make multiple transactions. By mastering the core concepts through problems like these, you will be well-prepared to tackle more challenging algorithmic problems.

Leave a Reply