Skip to content

Volume ITechnology

4.6.1 — Best Time to Buy and Sell Stock ​

LeetCode 121 · Easy · ★ Blind 75

The problem ​

You are given a list called prices, where prices[i] is the price of a share on day i. You may buy one share on one day and sell it on a later day. Return the biggest profit you can make. If no profit is possible, return 0.

prices = [7, 1, 5, 3, 6, 4]   →  5    (buy at 1 on day 1, sell at 6 on day 4)
prices = [7, 6, 4, 3, 1]      →  0    (the price only falls, so do not trade)

There are up to 100,000 days. Prices are between 0 and 10,000.

What the problem is really asking ​

Profit is selling price minus buying price. You must buy before you sell.

So fix a selling day. What is the best day to have bought? Obviously the cheapest day before it. So the best profit for selling on that day is "today's price minus the cheapest price so far".

The problem is really asking: as you walk through the days, what is the biggest gap between today's price and the lowest price you have seen so far?

The brute force, and where it wastes work ​

Try every buy day with every later sell day.

python
def maxProfit(prices):
    best = 0
    n = len(prices)
    for buy in range(n):
        for sell in range(buy + 1, n):
            best = max(best, prices[sell] - prices[buy])
    return best

That is about \frac{n^2}{2} pairs, roughly five billion for 100,000 days. Too slow.

The waste in one sentence: for each selling day, the only buy day that matters is the cheapest earlier one, but the brute force checks every earlier day again.

The idea ​

Walk through the days once. Carry one number: cheapest, the lowest price seen so far. At each day:

  1. Update cheapest if today is even cheaper.
  2. Work out what selling today would earn: price - cheapest.
  3. Keep the best of those profits.

You never need to look back at old days. The only thing the past can tell you is its lowest price, and you are already carrying it.

The solution ​

python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        cheapest = float('inf')                     # (1)
        best = 0                                    # (2)

        for price in prices:                        # (3)
            cheapest = min(cheapest, price)         # (4)
            best = max(best, price - cheapest)      # (5)

        return best
ts
function maxProfit(prices: number[]): number {
  let cheapest = Infinity;                          // (1)
  let best = 0;                                     // (2)

  for (const price of prices) {                     // (3)
    cheapest = Math.min(cheapest, price);           // (4)
    best = Math.max(best, price - cheapest);        // (5)
  }

  return best;
}

Line by line ​

(1) cheapest = float('inf'). The lowest price seen so far. Before we see any day, we start it at infinity, a value bigger than any real price. That way the first price we see is guaranteed to replace it. float('inf') is Python's infinity, and Infinity is the TypeScript one.

(2) best = 0. The best profit so far. Starting at 0, not at some negative number, matters. If prices only fall, every "profit" would be negative, and best simply stays 0. That gives the "do not trade" answer the problem asks for.

(3) Walk the days in order. Because we only walk forward, any buy price we use comes from an earlier day (or today). We can never "buy in the future".

(4) Update the cheapest price. If today is cheaper than every earlier day, it becomes the new best day to have bought.

(5) Try selling today. price - cheapest is the profit from buying on the cheapest day so far and selling today. Keep it if it beats best.

You might notice that line (4) runs before line (5). So if today is the new cheapest day, line (5) computes "buy today and sell today". That is not a real trade. But its profit is exactly 0, and best is never below 0, so it changes nothing. Writing it this way saves an extra if.

Trace ​

Take prices = [7, 1, 5, 3, 6, 4].

DayPricecheapest after (4)Profit today, price − cheapestbest after (5)
07700
11100
25144
33124
46155
54135

The answer is 5: buy at 1 on day 1, sell at 6 on day 4.

Complexity, derived ​

Time. The loop runs once per day, n times. Each turn does one min and one max, which is constant work. So the time is O(n).

Space. Two numbers, cheapest and best. The extra memory is O(1).

Edge cases ​

  • Prices only fall. Every profit is 0 or negative, so best stays 0.
  • One day. You cannot buy and sell on different days, so the answer is 0. The code gives 0 because the only "profit" is p - p = 0.
  • The cheapest day comes last, like [3, 5, 1]. The best trade is buy at 3, sell at 5. When the 1 arrives, cheapest drops to 1, but there are no later days, and best is already 2.

Is this really a sliding window? ​

The NeetCode list puts this problem under sliding window. You can see it that way: the window runs from the buy day to the sell day, and its left edge jumps forward whenever a cheaper price appears.

It is clearer, though, to see it as carrying the best answer so far. At each day, you work out the best you can do using only what you carried from yesterday. That is the seed of dynamic programming, which is 4.23.

There is also a link to Maximum Subarray. Turn the prices into daily changes: [7, 1, 5, 3, 6, 4] becomes [-6, 4, -2, 3, -2]. The biggest-sum stretch of those changes is 4, -2, 3, which adds to 5. That is the same answer. See 4.26.1.

Variations you will meet ​

Each step up the ladder changes what you must carry from day to day.

  • Buy and Sell Stock II. You may trade as many times as you like. Take every rise from one day to the next. See 4.26.
  • With Cooldown. After selling, you must wait a day before buying. Now you must track which state you are in: holding a share, just sold, or free. That is dynamic programming, in 4.24.3.
  • With a fee, or at most k trades. More states to carry.

The ladder shows when a simple running choice stops working: as soon as today's best move depends on a restriction left by an earlier move, you need dynamic programming.

What the interviewer will push on ​

"Why start best at 0 instead of a very negative number?" They are checking that you read the problem. If no profit is possible, the answer is 0, not a loss.

"Why start cheapest at infinity?" So the first price always replaces it, with no special case for day 0.

"Can buying and selling happen on the same day in your code?" In line (5) it can, but the profit is 0, so it never changes the answer.

"What if you could make two trades?" That is a harder problem. Carry four running values: best after first buy, after first sell, after second buy, after second sell.

One thing to volunteer: point out that you only need the past's minimum, not the past itself. That is why one pass and two variables are enough.

Next: 4.6.2 Longest Substring Without Repeating Characters. The first real window, with a rule for when its left edge moves.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet