LeetCode #121: Best Time to Buy and Sell Stock — Master the One-Pass Array Pattern

LeetCode Problem: Best Time to Buy and Sell Stock
Difficulty: Easy
Topics: Array, Greedy, Dynamic Programming
Series: LeetCode Interview Preparation — From Beginner to Expert

After learning Two Sum, it is time to learn another pattern that appears constantly in coding interviews:

Track the best opportunity you've seen so far while scanning the array once.

LeetCode's Best Time to Buy and Sell Stock looks like a simple stock-market problem, but it teaches an extremely important interview technique:

Maintain a running minimum and calculate the best answer at every step.

The Problem

You are given an array prices where:

prices[i]

represents the price of a stock on day i.

You want to choose:

• one day to buy
• a later day to sell

Your goal is to maximize your profit.

If you cannot make any profit, return:

0

Example

Input:
prices = [7, 1, 5, 3, 6, 4]

Output:
5

Why?

Buy at:

1

and sell at:

6

Profit:

6 - 1 = 5

The Important Rule

There is one critical constraint:

You must buy before you sell.

For example:

[7, 1, 5]

You cannot buy at 5 and sell at 1.

The order matters.

This is what makes the problem more interesting than simply finding the largest difference between two numbers.

First Approach: Brute Force

The simplest solution is to try every possible buying day and every possible selling day.

For every pair:

buy day < sell day

calculate:

profit = selling price - buying price

and keep the maximum.

Brute-Force Code

def maxProfit(prices):
    max_profit = 0

    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            profit = prices[j] - prices[i]
            max_profit = max(max_profit, profit)

    return max_profit

This solution works.

But there is a problem.

We are checking almost every possible pair.

Complexity of Brute Force

If there are n days:

Time Complexity: O(n²)
Space Complexity: O(1)

For a small input, that's fine.

But with millions of prices, checking every combination becomes expensive.

Can we solve it in one pass?

Yes.

The Key Observation

Imagine we're currently on day i.

We want to sell today.

What is the best possible profit?

Simple:

Today's Price - Lowest Price Before Today

So we don't actually need to remember every previous price.

We only need:

minimum price seen so far

and:

maximum profit seen so far

That's the entire trick.

The One-Pass Strategy

We'll maintain two variables:

min_price
max_profit

Initially:

min_price = infinity
max_profit = 0

Then scan the array from left to right.

For every price:

Step 1

Update the cheapest buying price:

min_price = min(min_price, price)

Step 2

Calculate today's possible profit:

profit = price - min_price

Step 3

Update the best profit:

max_profit = max(max_profit, profit)

That's it.

Optimized Python Solution

def maxProfit(prices):
    min_price = float('inf')
    max_profit = 0

    for price in prices:
        min_price = min(min_price, price)

        profit = price - min_price

        max_profit = max(max_profit, profit)

    return max_profit

Let's Understand It Step by Step

Consider:

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

We'll start with:

min_price = ∞
max_profit = 0

Day 1 — Price = 7

Current price:

7

Cheapest price so far:

7

Potential profit:

7 - 7 = 0

So:

min_price = 7
max_profit = 0

Day 2 — Price = 1

Current price:

1

We found a cheaper buying opportunity.

min_price = 1

Profit:

1 - 1 = 0

So:

max_profit = 0

Day 3 — Price = 5

Current price:

5

Minimum price remains:

1

Potential profit:

5 - 1 = 4

Therefore:

max_profit = 4

Day 4 — Price = 3

Minimum price:

1

Potential profit:

3 - 1 = 2

Our previous profit was better:

max_profit = 4

Day 5 — Price = 6

Minimum price:

1

Potential profit:

6 - 1 = 5

New maximum:

max_profit = 5

Day 6 — Price = 4

Potential profit:

4 - 1 = 3

No improvement.

Final answer:

5

Dry Run Table

Final answer:

5

Why Does This Work?

Suppose today's price is:

10

To maximize today's profit, we want the cheapest possible price before today.

Suppose we've already seen:

7
5
3
8

The best buying price is:

3

Therefore:

profit = 10 - 3
       = 7

There is no reason to remember the other buying prices.

The cheapest one dominates them.

That's the core optimization.

The Interview Insight

This problem teaches an extremely reusable thought process:

What information from the past is actually necessary to make the best decision now?

Instead of storing everything:

7, 1, 5, 3, ...

we compress the history into:

minimum price so far

This is a powerful technique.

Complexity Analysis

We scan the array exactly once.

For each price, we perform constant-time operations.

Therefore:

Time Complexity

O(n)

Space Complexity

O(1)

This is a huge improvement over brute force:

O(n²) → O(n)

while using constant extra space.

A More Concise Python Solution

Once you understand the logic, you can write:

def maxProfit(prices):
    min_price = prices[0]
    max_profit = 0

    for price in prices[1:]:
        max_profit = max(max_profit, price - min_price)
        min_price = min(min_price, price)

    return max_profit

Both versions are valid.

For interviews, prioritize clarity over cleverness.

Important Edge Cases

Interviewers often test edge cases.

Case 1: Prices Always Decrease

prices = [7, 6, 4, 3, 1]

There is no profitable transaction.

Answer:

0

Case 2: Only One Day

prices = [5]

You cannot buy and sell on the same day.

Answer:

0

Case 3: Two Days

prices = [2, 5]

Buy at:

2

Sell at:

5

Profit:

3

Answer:

3

Case 4: Same Prices

prices = [5, 5, 5, 5]

No profit.

Answer:

0

Common Mistake #1: Finding Minimum and Maximum Independently

A common incorrect solution is:

minimum = minimum(prices)
maximum = maximum(prices)

profit = maximum - minimum

This is not always correct.

Why?

Because the minimum price must occur before the maximum price.

Consider:

[10, 8, 6, 4, 2]

Minimum:

2

Maximum:

10

Difference:

8

But you cannot buy at 2 and sell at 10.

The 2 occurs after 10.

Therefore, the chronological order matters.

Common Mistake #2: Using the Current Minimum After Selling

The buying price must always come from an earlier day.

That's why the algorithm scans from left to right.

The current state represents:

best buying opportunity so far

This automatically guarantees:

buy → sell

in the correct order.

Common Mistake #3: Returning Negative Profit

If prices continually decrease:

[9, 7, 5, 3]

you shouldn't return:

-6

The problem says that if no profitable transaction exists, return:

0

That's why:

max_profit = 0

is important.

Can This Be Solved Using Dynamic Programming?

Yes.

You can think of the problem as maintaining the best state at every point.

But implementing a full DP array would be unnecessary.

For this problem, we only need two pieces of information:

minimum price so far
maximum profit so far

Therefore, the DP state can be compressed into two variables.

This is an important optimization concept:

If you only need the previous state, you may not need an entire DP table.

Greedy Thinking

This problem is also commonly categorized as a Greedy problem.

At every point, we make a locally useful decision:

Keep the lowest buying price seen so far.

That information is sufficient to calculate the best possible profit if we sell today.

The locally optimal minimum price allows us to discover the globally optimal transaction.

How to Recognize This Pattern

During an interview, watch for phrases such as:

• "Maximum profit"
• "Best time"
• "Maximum difference"
• "Choose an earlier value"
• "Find the best pair"
• "One pass"
• "Previous elements"
• "Maximum gain"

Then ask:

Question 1

What information from previous elements matters?

Question 2

Can I maintain that information in a variable?

Question 3

Can I calculate the answer for the current element using that state?

For this problem:

Previous information:
minimum price

Current information:
today's price

Decision:
today's profit

Answer:
maximum profit

The General Pattern

This problem can be reduced to:

Scan Array
     ↓
Maintain Best Previous Value
     ↓
Calculate Current Candidate
     ↓
Update Global Answer

This pattern is extremely useful.

For example:

minimum so far
maximum so far
best profit so far
best difference so far
best score so far

Whenever a problem asks you to compare the current element with something from the past, consider whether a running state can eliminate nested loops.

Interview Follow-Up Questions

Once you've solved the basic problem, an interviewer may change the requirements.

Follow-Up 1: Unlimited Transactions

What if you can buy and sell multiple times?

This leads to a different problem and a different strategy.

Follow-Up 2: Transaction Fee

What if every transaction has a fee?

Now the profit calculation changes.

Follow-Up 3: Cooldown

What if after selling, you must wait one day before buying again?

This introduces a more interesting DP state.

Follow-Up 4: At Most Two Transactions

Now you need to track multiple transaction states.

This is where the problem becomes significantly more advanced.

Follow-Up 5: At Most K Transactions

Now you enter a broader family of dynamic programming problems.

A simple Easy problem can therefore become a gateway to several Medium and Hard interview problems.

From Easy Problem to Interview Pattern

This is what you should take away.

Don't memorize:

min_price = min(min_price, price)

Instead, understand:

"I need the cheapest valid buying opportunity before the current selling day."

That sentence naturally leads to:

min_price

Then:

"If I sell today, what profit can I make?"

That leads to:

price - min_price

Finally:

"What's the best profit I've seen?"

That leads to:

max_profit

This is how strong problem solvers approach LeetCode.

Interview Cheat Sheet

Problem:
Maximum profit from one buy + one sell.

Brute Force:
Try every buy/sell combination.

Brute Force:
O(n²) time
O(1) space

Optimized:
One-pass scan.

Maintain:
minimum price so far
maximum profit so far

At every price:

min_price = min(min_price, price)

profit = price - min_price

max_profit = max(max_profit, profit)

Final:
O(n) time
O(1) space

Practice Problems

After solving this problem, try variations involving:

1. Maximum difference between two elements with ordering constraints.
2. Maximum profit with unlimited transactions.
3. Maximum profit with transaction fees.
4. Maximum profit with cooldown.
5. Maximum profit with at most two transactions.
6. Maximum profit with at most k transactions.

These problems will gradually introduce Greedy and Dynamic Programming patterns.

Final Takeaway

LeetCode #121 is not really about stocks.

It is about learning how to replace unnecessary comparisons with a small amount of carefully maintained state.

Instead of:

Compare every pair
        ↓
O(n²)

we do:

Remember the cheapest previous price
        ↓
Calculate today's possible profit
        ↓
Keep the best profit
        ↓
O(n)

The most important question to ask yourself in similar problems is:

"What is the minimum information I need to remember from the past to make the best decision now?"

Master that question and you'll start seeing optimization opportunities across many LeetCode problems.