Best Time to Buy and Sell Stock#

Given an array where each entry is the price of a stock on a given day, find the maximum profit from buying on one day and selling on a later day. You must buy before you sell. If no profitable trade exists, return 0.

Example#

Input: prices = [7, 1, 5, 3, 6, 4] Output: 5, by buying at price 1 on day 2 and selling at price 6 on day 5.

Brute force#

Try every pair of a buy day and a later sell day, compute the profit, and keep the maximum. This checks far more pairs than necessary.

• Time: O(n^2).
• Space: O(1).

Optimal approach#

Sweep through the prices once while tracking the lowest price seen so far as a candidate buy point. At each day, the best profit ending there is the current price minus that running minimum. Update the running minimum and the best profit as you go. This is a sliding view over the array where the left edge is the cheapest earlier day.

Python solution#

1def max_profit(prices):
2    min_price = float("inf")
3    best = 0
4    for price in prices:
5        if price < min_price:
6            min_price = price
7        else:
8            best = max(best, price - min_price)
9    return best

Complexity#

• Time: O(n), a single pass.
• Space: O(1), two scalar variables.

This problem is a one-pass variant of the sliding window technique. Keep going with the 60-day challenge.