Best Time to Buy and Sell Stock leetcode question – Python Solution

Introduction

In this tutorial, we will explore the “Best Time to Buy and Sell Stock” interview question and provide various solutions in Python. The problem statement is as follows:

You are given an array of stock prices, where the ith element represents the price of a given stock on day i. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Write a function max_profit(prices) that returns the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Approach 1: Brute Force

The brute force approach involves considering each pair of days (buying and selling) and calculating the corresponding profit. We can keep track of the maximum profit found so far and update it whenever a higher profit is obtained.

Let’s see the implementation:

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]
            if profit > max_profit:
                max_profit = profit
    return max_profit

The time complexity of this brute force solution is O(n^2), where n represents the length of the prices array. The outer loop runs n times, and for each iteration, the inner loop runs n-i-1 times. Thus, the total number of iterations is (n-1) + (n-2) + … + 1, which is equal to n(n-1)/2.

The space complexity is O(1) since we only need a constant amount of extra space to store the maximum profit.

Approach 2: One Pass

The brute force approach is inefficient because it considers all possible pairs of buying and selling days. However, we can optimize the solution by keeping track of the minimum buying price encountered so far and calculating the maximum profit based on it.

Let’s see the implementation:

def max_profit(prices):
    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

In this approach, we iterate through the prices array and update the minimum buying price if we encounter a lower price. If the difference between the current price and the minimum price is greater than the maximum profit, we update the maximum profit accordingly.

The time complexity of this approach is O(n) since we iterate through the prices array once.

The space complexity is O(1) since we only need a constant amount of extra space to store the minimum price and maximum profit.

Approach 3: Dynamic Programming

In this approach, we can solve the problem using dynamic programming. We create an array, dp, of length n, where dp[i] represents the maximum profit we can achieve by selling the stock on day i. We initialize dp[0] to 0 since we cannot sell on the first day. For each subsequent day, dp[i] is calculated as the maximum of dp[i-1] and prices[i] – min_price, where min_price is the minimum price encountered so far.

Let’s see the implementation:

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

The time complexity of this approach is O(n) since we iterate through the prices array once.

The space complexity is O(n) since we create an additional array, dp, of length n to store the maximum profit at each day.

Summary

In this tutorial, we explored different approaches to solve the “Best Time to Buy and Sell Stock” interview question in Python. We started with a brute force solution that considers all pairs of buying and selling days. Then, we optimized it to a one-pass solution by keeping track of the minimum buying price and maximum profit. Finally, we presented a dynamic programming solution that uses an additional array to store the maximum profit at each day.

Here is a summary of the time and space complexities for each approach:

Approach	Time Complexity	Space Complexity
Brute Force	O(n^2)	O(1)
One Pass	O(n)	O(1)
Dynamic Programming	O(n)	O(n)

It is recommended to use the one-pass or dynamic programming approach to obtain a more efficient solution.