LeetCode: Best Time to Buy and Sell Stock — Optimal Solution Explained

LeetCode: Best Time to Buy and Sell Stock — Optimal Solution Explained

Table of Content

• Introduction
• Intuition/Solution
• Step-by-Step Visual Guide
• Implementation Code

Introduction

The problem is simple: given an array of prices representing the stock prices for a company in chronological order, you have the opportunity to buy one stock and sell it at a later time. Your goal is to maximize your profit. Keep in mind that you must buy before you can sell.

While there are various ways to approach this problem, today, we will explore the greedy algorithm approach

We will guide you step by step, using clear visuals to demonstrate how the solution works with time complexity of O(n) and space complexity of O(1)

Intuition/Solution

The intuition behind the solution for the “Best Time to Buy and Sell Stock” problem is to track the minimum price min_price seen so far and the maximum profit max_profit obtained at each step. In other words, min_price would be when you would Buy and max_profit would be when you would Sell.

As we iterate through the array of stock prices, we’re looking for two things:

1. The lowest price we’ve seen so far, because that’s our best opportunity to buy low.
2. The highest profit we can make based on the lowest price seen so far, since we want to sell at a higher price.

We keep track of these two values while iterating through the array, updating them as we find better opportunities to buy and sell.

Here’s the step-by-step intuition:

1. Initialize min_price to the first stock price in the array and max_profit to 0.
2. Iterate through the array of stock prices starting from the second price.
3. For each price, check if it’s lower than the current min_price. If it is, update min_price with the current price. This step ensures we’re always considering the lowest price seen so far for potential buying.
4. Calculate the potential profit by subtracting the current min_price from the current price. If this potential profit is greater than the current max_profit, update max_profit with the new value. This step helps us find the highest profit we can make based on the lowest price seen so far.
5. Continue iterating through the array until you’ve checked all the prices.
6. After finishing the iteration, max_profit will hold the maximum profit that can be achieved.

This approach ensures that we’re always considering the best buying and selling opportunities as we go through the stock prices. The key intuition is to keep track of the minimum price and maximum profit simultaneously, updating them as we find better opportunities in the array.

Step-by-Step Visual Guide

I’ll represent the solution visually using a table to show the changes in min_price and max_profit at each step:

Initialization
---------------
min_price = prices[0] = 7
max_profit = 0 
---------------

prices = [7, 1, 5, 3, 6, 4]
          ^  ^  ^  ^  ^  ^
 Steps:   1  2  3  4  5  6

Step | Current Price | min_price | max_profit
-----+---------------+-----------+-----------
  1  |       7       |     7     |     0
  2  |       1       |     1     |     0
  3  |       5       |     1     |     4 (5 - 1)
  4  |       3       |     1     |     4 (no change)
  5  |       6       |     1     |     5 (6 - 1)
  6  |       4       |     1     |     5 (no change)

At each step, we compare the current price with the min_price and update min_price if the current price is lower. We also calculate the profit with the current price and min_price, and update max_profit if a higher profit is found.

Implementation Code

Python

def max_profit(prices):
    min_price = float('inf')  # Initialize the minimum price as infinity
    max_profit = 0  # Initialize the maximum profit as 0

    for price in prices:
        # Update the minimum price if the current price is lower
        min_price = min(min_price, price)

        # Calculate the profit if the stock is sold at the current price
        profit = price - min_price

        # Update the maximum profit if the calculated profit is higher
        max_profit = max(max_profit, profit)

    return max_profit

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

Javascript

function maxProfit(prices) {
    let min_price = prices[0];
    let max_profit = 0;

    for (let i = 1; i < prices.length; i++) {
        min_price = Math.min(min_price, prices[i]);
        max_profit = Math.max(max_profit, prices[i] - min_price);
    }

    return max_profit;
}