LeetCode · #121

Best Time to Buy and Sell Stock Solution

Given an array prices where prices[i] is the price on day i, return the maximum profit from one buy and one sell.

Section One · Problem

Problem Statement

🏷️

Difficulty

Easy

🔗

LeetCode

Problem #121

🏗️

Pattern

Sliding Window — track min so far

You are given an array prices where prices[i] is the price of a stock on day i. You want to maximize profit by choosing a single day to buy and a single future day to sell. Return the maximum profit, or 0 if no profit is possible.

Example

 Input: prices = [7, 1, 5, 3, 6, 4]
Output: 5 // Buy on day 1 (price=1), sell on day 4 (price=6) → profit = 5 

Constraints

• 1 ≤ prices.length ≤ 10⁵ • 0 ≤ prices[i] ≤ 10⁴

Section Two · Approach 1

Brute Force — O(n²)

For every day i, check every future day j > i and compute prices[j] - prices[i]. Track the maximum difference.

Problem: O(n²) pairs. We only need to track the minimum price seen so far — at each day, the best profit is prices[i] - minSoFar. One pass, O(1) space.

Java — Brute Force

 class Solution {
public int maxProfit(int[] prices) {
int max = 0;
for (int i = 0; i < prices.length; i++)
for (int j = i + 1; j < prices.length; j++)
                max = Math.max(max, prices[j] - prices[i]);
return max;
    }
}

Python — Brute Force

 class Solution:
def maxProfit(self, prices: list[int]) -> int:
        max_profit = 0 for i in range(len(prices)):
for j in range(i + 1, len(prices)):
                max_profit = max(max_profit, prices[j] - prices[i])
return max_profit

Metric	Value
Time	O(n²)
Space	O(1)

Section Three · Approach 2

One Pass — O(n)

Scan left to right, tracking the minimum price seen so far. At each day, compute profit as price - minPrice. Update the maximum profit. The minimum price acts as the left pointer of a sliding window — it resets whenever a cheaper buy opportunity is found.

💡 Mental model: You're walking down a timeline of prices. You carry a sign showing the cheapest price you've ever passed. At each new day, you ask: "If I had bought at that cheapest price, how much would I make selling today?" You record the best answer. If today's price is even cheaper, you update your sign.

Algorithm

Step 1: minPrice = ∞, maxProfit = 0.
Step 2: For each price: update minPrice = min(minPrice, price).
Step 3: Update maxProfit = max(maxProfit, price - minPrice).
Step 4: Return maxProfit.

🎯 When to recognize this pattern:

Any problem asking for the maximum difference between two elements where the smaller must come first — think track-min-so-far.
This is a degenerate sliding window where the left boundary only moves forward when a new minimum is found.
The same idea extends to maximum subarray (Kadane's algorithm) and stock problems with multiple transactions.

Section Four · Trace

Visual Walkthrough

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

One Pass — track min price, compute profit at each step

Section Five · Implementation

Code — Java & Python

Java — One Pass

 class Solution {
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int price : prices) {
            minPrice = Math.min(minPrice, price);
            maxProfit = Math.max(maxProfit, price - minPrice);
        }
return maxProfit;
    }
}

Python — One Pass

 class Solution:
def maxProfit(self, prices: list[int]) -> int:
        min_price = float('inf')
        max_profit = 0 for price in prices:
            min_price = min(min_price, price)
            max_profit = max(max_profit, price - min_price)
return max_profit

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute Force	O(n²)	O(1)	Check all buy/sell pairs
One Pass ← optimal	O(n)	O(1)	Track min price, compute profit at each step

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Decreasing prices	`[7, 6, 4, 3, 1]`	No profit possible → return 0. Profit is never positive.
Single day	`[5]`	Can't buy and sell on same day → 0.
All same price	`[3, 3, 3]`	Profit = 0 everywhere.
Best at end	`[2, 4, 1, 7]`	Min shifts to 1 on day 2, best profit at day 3: 7-1=6.
Best at start	`[1, 5, 2, 3]`	Min stays 1, best profit is 5-1=4 on day 1.

⚠ Common Mistake: Computing max(prices) - min(prices) without checking that the min comes before the max. The minimum price might occur after the maximum, making the trade impossible. Tracking minSoFar as you scan left-to-right guarantees you only consider valid buy-before-sell pairs.

← Back to Sliding Window problems

LearningTree

LC 121 · Best Time to Buy and Sell Stock — Solution & Explanation | DSA Guide