Best Time to Buy and Sell Stock: Greedy Pattern

Learning Outcome

After this lesson, you should be able to convert the "choose buy and sell days" brute force into a one-pass greedy scan.

Problem Statement

Given prices, where prices[i] is the stock price on day i, return the maximum profit from one buy and one later sell. If no profit is possible, return 0.

Brute Force Approach

Try every buy day and every later sell day. Compute prices[sell] - prices[buy] and keep the best profit.

This checks the rule correctly, but it costs O(n^2) because every day can be paired with many later days.

Optimized Approach

While scanning left to right, keep the minimum price seen so far. If you sell today, the best valid buy day must be one of the earlier days, so today profit is price - minPrice.

This works because every sell day only needs the cheapest earlier buy day, not all earlier days.

Exact Pseudocode

minPrice = infinity
best = 0
for price in prices:
  minPrice = min(minPrice, price)
  best = max(best, price - minPrice)
return best
  

Reference Code

class Solution:
    def maxProfit(self, prices):
        min_price = float("inf")
        best = 0

        for price in prices:
            min_price = min(min_price, price)
            best = max(best, price - min_price)

        return best
  

Sample Dry Run

Complexity

Edge Cases

• Prices always decrease, such as [7, 6, 4, 3, 1].
• Only one day or empty input if allowed by platform constraints.
• Best buy day appears before the best sell day, not after.

Interview Checklist

• Emphasize "buy before sell".
• Track the cheapest price seen so far.
• Return 0 when no positive profit exists.

FAQs