{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Best Time to Buy and Sell Stock – Solution & Complexity

Interview solutions
/
Best Time to Buy and Sell Stock
Quick practice for Best Time to Buy and Sell Stock: 3 reasoning beats, no typing

Watch: Best Time to Buy and Sell Stock in one pass

Comparing every pair of days is O(n²). Instead, walk the prices once and remember the cheapest price so far. Each day, selling today earns price − cheapest; keep the best of those. One pass, O(n) time and O(1) space.

Solution Walkthrough

  1. Step 1: Understand the Goal

    • You need choose one day to buy and a later day to sell.
    • Profit is sell_price - buy_price.
    • If every later price is lower, the best valid answer is 0 because you can skip the trade.

  2. Step 2: Consider the Brute Force Idea

    • A direct solution checks every possible buy day with every later sell day.
    • This finds the correct answer, but it repeats a lot of work.
    • With two nested loops, the time complexity is O(n²).
    def max_profit(prices: list[int]) -> int:
    best = 0
    for buy in range(len(prices)):
        for sell in range(buy + 1, len(prices)):
            best = max(best, prices[sell] - prices[buy])
    return best

  3. Step 3: Track the Cheapest Buy Price

    • When scanning prices from left to right, the best buy day before today is simply the lowest price seen so far.
    • For each current price, calculate the profit from selling today after buying at that lowest earlier price.
    • Then update the best profit if today gives a better one.

  4. Step 4: Build the One-Pass Loop

    • Initialize min_price to a very large value and best to 0.
    • For each price, first update the minimum price seen so far.
    • Then compare the current possible profit against the best answer.
    def max_profit(prices: list[int]) -> int:
    min_price = float('inf')
    best = 0
    for price in prices:
        min_price = min(min_price, price)
        best = max(best, price - min_price)
    return best

  5. Step 5: Final Solution and Complexity

    • The scan preserves the rule that buying happens before selling because min_price only comes from days already visited.
    • Time complexity is O(n) because each price is processed once.
    • Space complexity is O(1) because only two variables are stored.
    def max_profit(prices: list[int]) -> int:
    min_price = float('inf')
    best = 0

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

    return best
Learn the Sliding Window pattern: recognition cues, invariant, and ordered practice →

FAQ

See also

Practice Best Time to Buy and Sell Stock online (run code in the browser)Coin Change solution (medium)House Robber solution (medium)House Robber II solution (medium)Jump Game solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?