Best Time to Buy and Sell Stock – LeetCode 121

Best Time to Buy and Sell Stock – LeetCode 121 (O(n) One-Pass Solution)

The Best Time to Buy and Sell Stock problem from LeetCode 121 is a classic array and greedy problem frequently asked in coding interviews. The goal is to maximize profit by choosing a single day to buy and a later day to sell.

Problem Statement

You are given an array prices, where prices[i] represents the price of a stock on day i. You may complete at most one transaction (buy once and sell once).

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

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

If no profit is possible, return 0.

---

Key Observations

• You must buy before you sell
• Only one transaction is allowed
• The selling day must come after the buying day

---

Approach 1: Brute Force (Not Optimal)

The brute force approach checks every possible pair of buying and selling days and calculates the profit.

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

Complexity

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

This approach works but is too slow for large inputs and is not suitable for interviews.

---

Optimal Approach: One-Pass Greedy Solution

The best solution uses a greedy strategy and scans the array only once. We track the minimum buying price so far and calculate the maximum profit at each step.

Core Idea

• Always buy at the lowest price seen so far
• At each day, compute profit if sold today
• Keep updating the maximum profit

Python Code

class Solution:
    def maxProfit(self, prices):
        buy_price = prices[0]
        profit = 0

        for price in prices[1:]:
            if price < buy_price:
                buy_price = price
            else:
                profit = max(profit, price - buy_price)

        return profit

Complexity

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

This solution is optimal and works efficiently even for large datasets.

---

Why This Solution Works

By keeping track of the lowest price encountered so far, we ensure that every profit calculation respects the rule that buying must happen before selling. The maximum profit is updated only when a better selling opportunity appears.

---

Interview Insight

• Demonstrates greedy decision making
• Uses constant extra space
• Shows understanding of real-world constraints

This pattern is widely used in stock-related and profit-maximization problems.

---

Conclusion

The one-pass greedy approach is the best solution for LeetCode 121. It avoids unnecessary comparisons, runs in linear time, and uses constant space. Mastering this technique will help solve many similar problems efficiently.