← DSA Atlas
Dedicated problem page · #121

Best Time to Buy and Sell Stock

EasySliding WindowRunning minimum with best forward differenceSingle-pass scan (degenerate sliding window)
Solve on LeetCode ↗
121
EasySliding WindowSingle-pass scan (degenerate sliding window)Running minimum with best forward difference

Best Time to Buy and Sell Stock

Given an array prices where prices[i] is the price of a stock on day i, choose one day to buy and a later day to sell to maximize profit. Return the maximum profit, or 0 if no profitable transaction is possible.

Open official problem prompt ↗
In plain English

Find the largest increase from an earlier day's price to a later day's price.

Picture it like this

Walking forward while remembering the cheapest price you have passed; at each stall you check how much you'd make reselling there against that cheapest memory.

Example
Input
prices = [7,1,5,3,6,4]
Output
5
Why
Buy on day 1 at price 1 and sell on day 4 at price 6 for a profit of 6 - 1 = 5.
Constraints
1 <= prices.length <= 10^50 <= prices[i] <= 10^4
Pattern lesson

See the pattern, then code

Running minimum with best forward difference
Recognition clue

Maximize the gap between a later value and an earlier smaller value in a single left-to-right sequence — buy must precede sell.

↗
Sliding Window

Longest, shortest, maximum, or minimum contiguous subarray or substring.. As you scan, the best sell price for today is today's price minus the smallest price seen so far, so keep the running minimum and the best difference.

New words, made simpleKnow these before the algorithm
Running minimum
The lowest price observed from day 0 up to the current day.
Forward difference
current price minus the running minimum — the profit if you sell today.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
All pairs of days

Quadratic and unnecessary for a strictly forward comparison.

Try every buy day paired with every later sell day.

Time O(n^2)Space O(1)
Best choiceRunning minimum single pass

Linear time, constant space, and trivially correct.

Keep the cheapest price so far and the best sell-today profit in one scan.

Time O(n)Space O(1)
The rule we keep true

Invariant

At every day, min_price is the smallest price among all previous days, and best is the maximum profit achievable selling on or before the current day.

Why this is correct

Reasoning

The optimal sell day's profit equals its price minus the minimum price among all earlier days. By carrying that minimum forward, each day's best possible profit is computed in O(1), and the running maximum over all days is the global answer.

The algorithm in three movesSay these aloud before coding
1Track the minimum price seen so far, starting at infinity

min_price becomes 1 at day 1

2For each price, if it is a new minimum, update the minimum

day 4: 6 - 1 = 5

3Otherwise compute price - minimum and update the best profit

best = 5

4Return the best profit (0 if never positive)

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
70
11
52
33
64
45
1 · Read7 then 1
2 · AskNew minimum?
3 · Update statemin_price = 1
4 · Resultno profit recorded yet
Key takeaway

Buying at the lowest earlier price (1) and selling at 6 yields the maximum profit of 5.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-4Initialize

    min_price starts at infinity so the first price always becomes the minimum; best starts at 0 for the no-trade case.

  2. 2
    Lines 6-7Update minimum

    A lower price becomes the new cheapest buy point.

  3. 3
    Lines 8-9Update profit

    Otherwise selling today may beat the best profit seen so far.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Monotonically decreasing prices return 0 (no profitable trade)
  • Single day returns 0
  • All equal prices return 0
  • Strictly increasing prices return last minus first
!

Common beginner mistakes

  • Allowing the sell day to precede the buy day
  • Initializing best to negative infinity and returning a negative 'profit' instead of 0
  • Confusing this with the multiple-transaction variant (this problem allows exactly one buy and one sell)
Check your understanding

Why can we update the minimum and the profit in a single pass without revisiting earlier days?

More in Sliding Window

#3Longest Substring Without Repeating CharactersVariable-size sliding window with last-seen index#424Longest Repeating Character ReplacementVariable-size window constrained by replaceable slots#76Minimum Window SubstringShrinkable window covering a multiset requirement#30Substring with Concatenation of All WordsWord-aligned sliding window over fixed-length tokens#209Minimum Size Subarray SumShrinking window on a sum threshold#239Sliding Window MaximumMonotonic decreasing deque