LeetCode 121: Best Time to Buy and Sell Stock Solution in Python – A Step-by-Step Guide

What Is LeetCode 121: Best Time to Buy and Sell Stock?

In LeetCode 121: Best Time to Buy and Sell Stock, you’re given an array prices where prices[i] is the stock price on day i. Your task is to find the maximum profit you can achieve by buying on one day and selling on a later day. If no profit is possible, return 0. For example, with prices = [7, 1, 5, 3, 6, 4], the maximum profit is 5 (buy at 1, sell at 6).

Problem Statement

• Input: An integer array prices.
• Output: An integer—the maximum profit from one buy and one sell.
• Rules:
• Buy before sell (sell day > buy day).
• Single transaction only.
• Return 0 if no profit possible.

Constraints

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

Examples

• Input: prices = [7, 1, 5, 3, 6, 4]
• Output: 5
• Why: Buy at 1 (day 1), sell at 6 (day 4) = 6 - 1 = 5.
• Input: prices = [7, 6, 4, 3, 1]
• Output: 0
• Why: Prices only decrease, no profit possible.
• Input: prices = [2, 4, 1]
• Output: 2
• Why: Buy at 2, sell at 4 = 4 - 2 = 2.

Understanding the Problem: Maximizing the Gain

To solve LeetCode 121: Best Time to Buy and Sell Stock in Python, we need to find the maximum difference between two elements in the array where the smaller (buy) comes before the larger (sell). A naive approach—checking every buy-sell pair—takes O(n²) time, which is too slow for up to 10⁵ elements. Instead, we’ll use smarter strategies:

• Best Solution (One-Pass): O(n) time, O(1) space—tracks the minimum price seen so far.
• Alternative Solution (Brute Force with Optimization): O(n²) time, O(1) space—simpler but slower.

Let’s dive into the Best Solution—the one-pass approach—and break it down step-by-step.

Best Solution: One-Pass with Minimum Tracking

Why This Is the Best Solution

The one-pass approach is the gold standard because it’s lightning-fast—O(n) time—and uses O(1) space. It scans the array once, keeping track of the minimum price seen so far and updating the maximum profit whenever a higher sell price is found. It’s like walking through the market, noting the cheapest price you’ve seen and calculating your potential profit each day—efficient and elegant!

How It Works

Here’s the strategy:

• Step 1: Initialize Variables:
• min_price: Lowest price seen so far (start with infinity).
• max_profit: Best profit possible (start at 0).
• Step 2: Scan the Array:
• For each price:
• Update min_price if current price is lower.
• Calculate potential profit (current price - min_price).
• Update max_profit if potential profit is higher.
• Step 3: Return the Result:
• max_profit is the answer.

Step-by-Step Example

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

• Initialize: min_price = float('inf'), max_profit = 0.
• Day 0 (7):
• min_price = min(inf, 7) = 7.
• Profit = 7 - 7 = 0.
• max_profit = 0.
• Day 1 (1):
• min_price = min(7, 1) = 1.
• Profit = 1 - 1 = 0.
• max_profit = 0.
• Day 2 (5):
• min_price = 1.
• Profit = 5 - 1 = 4.
• max_profit = 4.
• Day 3 (3):
• min_price = 1.
• Profit = 3 - 1 = 2.
• max_profit = 4.
• Day 4 (6):
• min_price = 1.
• Profit = 6 - 1 = 5.
• max_profit = 5.
• Day 5 (4):
• min_price = 1.
• Profit = 4 - 1 = 3.
• max_profit = 5.
• Result: 5.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # Step 1: Initialize variables
        min_price = float('inf')
        max_profit = 0

        # Step 2: Scan prices
        for price in prices:
            # Update minimum price seen so far
            min_price = min(min_price, price)
            # Update maximum profit if current profit is higher
            max_profit = max(max_profit, price - min_price)

        return max_profit

• Line 4-5: Set min_price to infinity, max_profit to 0.
• Line 8-11: Loop through prices:
• Line 10: Update min_price if current price is lower.
• Line 12: Update max_profit with max of current profit and previous max.
• Line 14: Return the maximum profit.
• Time Complexity: O(n)—single pass through array.
• Space Complexity: O(1)—just two variables.

This is a sleek profit tracker!

Alternative Solution: Brute Force with Optimization

Why an Alternative Approach?

The brute force approach with optimization is a straightforward fallback—O(n²) time, O(1) space. It checks every possible buy-sell pair but skips unnecessary comparisons by breaking early when prices decrease. It’s like manually testing every trade option with a slight tweak to save time—simple but not as fast.

How It Works

Here’s the plan:

• Step 1: Loop over each day as buy day.
• Step 2: For each buy day, check all later days as sell day.
• Step 3: Calculate profit for each pair, update max profit.
• Step 4: Optimize by breaking if price drops below buy price.

Step-by-Step Example

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

• Initialize: max_profit = 0.
• Buy Day 0 (7):
• Sell 1 (1): 1-7 = -6, skip.
• Sell 2 (5): 5-7 = -2, skip.
• Sell 3 (3): 3-7 = -4, skip.
• Sell 4 (6): 6-7 = -1, skip.
• Sell 5 (4): 4-7 = -3, skip.
• max_profit = 0.
• Buy Day 1 (1):
• Sell 2 (5): 5-1 = 4, max_profit = 4.
• Sell 3 (3): 3-1 = 2, max_profit = 4.
• Sell 4 (6): 6-1 = 5, max_profit = 5.
• Sell 5 (4): 4-1 = 3, max_profit = 5.
• Buy Day 2 (5):
• Sell 3 (3): 3-5 = -2, skip.
• Sell 4 (6): 6-5 = 1, max_profit = 5.
• Sell 5 (4): 4-5 = -1, skip.
• Result: 5.

Code for Brute Force Approach

Copy codeclass 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)):
                profit = prices[j] - prices[i]
                if profit > 0:
                    max_profit = max(max_profit, profit)

        return max_profit

• Line 4: Initialize max_profit.
• Line 6-9: Double loop for buy and sell days:
• Line 8: Calculate profit.
• Line 9-10: Update max_profit if positive.
• Time Complexity: O(n²)—nested loops.
• Space Complexity: O(1)—no extra space.

It’s a thorough but slow trader!

Comparing the Two Solutions

• One-Pass (Best):
• Pros: O(n) time, O(1) space, fast and elegant.
• Cons: Less obvious at first glance.
• Brute Force (Alternative):
• Pros: O(n²) time, O(1) space, simple logic.
• Cons: Much slower.

One-pass wins hands down.

Additional Examples and Edge Cases

• [2, 1]: 0 (no profit).
• [1, 2, 3]: 2 (1 to 3).
• [5]: 0 (single day).

Both handle these perfectly.

Complexity Breakdown

• One-Pass: Time O(n), Space O(1).
• Brute Force: Time O(n²), Space O(1).

One-pass is the clear winner.

Key Takeaways

• One-Pass: Track the min, max the gain!
• Brute Force: Check all pairs, optimize lightly!
• Profit: Buy low, sell high.
• Python Tip: Loops simplify—see [Python Basics](/python/basics).

Final Thoughts: Cash In Big

LeetCode 121: Best Time to Buy and Sell Stock in Python is a market challenge that rewards efficiency. The one-pass approach nails it with speed, while brute force offers a fallback with grit. Want more stock fun? Try LeetCode 122: Best Time to Buy and Sell Stock II or LeetCode 53: Maximum Subarray. Ready to profit? Head to Solve LeetCode 121 on LeetCode and make that trade today!