loading

Best Time to Buy and Sell Stock — Step-by-Step Visualization

easyLeetCode #121ArrayDynamic Programming

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

Algorithm Pattern

Two Pointers / Greedy

Key Idea

To maximize profit, we need to buy at the lowest possible price so far and sell at the highest price that appears *after* that purchase. We can achieve this in a single pass by keeping track of the minimum price encountered and calculating the potential profit at each step.

Step-by-Step Approach

  1. Initialize `minPrice` to infinity and `maxProfit` to 0.
  2. Iterate through the `prices` array.
  3. If the current price is less than `minPrice`, update `minPrice`.
  4. Else if the difference between the current price and `minPrice` is greater than `maxProfit`, update `maxProfit`.
  5. Return `maxProfit`.

Common Gotchas

  • You cannot sell a stock before you buy it. This is why we update `minPrice` first and then calculate profit.

Related Problems

← All problems