Best Time to Buy and Sell Stock – Solution & Complexity

Q: What is the time and space complexity of Best Time to Buy and Sell Stock?

The optimal Best Time to Buy and Sell Stock solution runs in `O(n)` time and `O(1)` space. Track the minimum price so far and the best profit in a single pass.

Q: What is the most efficient way to solve Best Time to Buy and Sell Stock?

Track the minimum price so far and the best profit in a single pass. This gives `O(n)` time complexity, and is a classic arrays and dynamic programming problem.

Q: How do you solve Best Time to Buy and Sell Stock in Python & JavaScript?

We provide a worked Best Time to Buy and Sell Stock solution in Python & JavaScript with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Best Time to Buy and Sell Stock an easy or hard interview question?

Best Time to Buy and Sell Stock is generally rated **Easy**. It tests arrays and dynamic programming, which are common coding-interview patterns.

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. 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. 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. 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. 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

Best Time to Buy and Sell Stock – Solution & Complexity

1. Understand the Goal

2. Consider the Brute Force Idea

3. Track the Cheapest Buy Price

4. Build the One-Pass Loop

5. Final Solution and Complexity

FAQ

What is the time and space complexity of Best Time to Buy and Sell Stock?

What is the most efficient way to solve Best Time to Buy and Sell Stock?

How do you solve Best Time to Buy and Sell Stock in Python & JavaScript?

Is Best Time to Buy and Sell Stock an easy or hard interview question?