1 / 1
06A/191
Best Time to Buy and Sell Stock
Problem Statement

You are given an array prices where prices[i] is the stock price on day i. Choose one day to buy and a later day to sell to maximize profit. If no profit is possible, return 0.

Examples

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

Output: 5

Explanation: Buy at 1 and sell at 6 for profit 5.

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

Output: 0

Explanation: Prices keep falling, so the best choice is no transaction.

Custom Notes
  • One transaction only.
  • Buy must happen before sell.
  • Profit today = today's price - minimum price seen earlier.
  • Memory hook: min so far, best profit so far.
  • Do not confuse this with the multiple-transactions stock problem.
Brute Force Approach : TC: SC:
1 / 3

Algorithm: Try every buy day with every later sell day.

Pseudo:

  • For each i, treat prices[i] as buy.
  • For each j > i, compute prices[j] - prices[i].
  • Track the maximum profit.

Time: O(n^2)

Space: O(1)

Why mention it: Straightforward baseline and makes the single-transaction constraint obvious.

Better Approach : TC: SC:
2 / 3

Algorithm: Precompute the best future sell price for each index and compare.

Pseudo:

  • Build a suffixMax array where suffixMax[i] is the maximum price from i to end.
  • For each day i, profit = suffixMax[i] - prices[i].
  • Track the maximum over all i.

Time: O(n)

Space: O(n)

Interview line: Good transition solution, but we can do the same in constant space.

Optimal Approach : TC: SC:
3 / 3

Algorithm: Maintain minPrice and update maxProfit while scanning once.

Pseudo:

  • Initialize minPrice = prices[0] and maxProfit = 0.
  • For each price, compute currentProfit = price - minPrice.
  • Update maxProfit with currentProfit.
  • Update minPrice = min(minPrice, price).

Time: O(n)

Space: O(1)

Key insight: The best buy for today is simply the minimum price that appeared before today.

PCode
1 / 3
bestProfit = 0

FOR buy from 0 to n - 1
    FOR sell from buy + 1 to n - 1
        profit = prices[sell] - prices[buy]
        bestProfit = max(bestProfit, profit)

RETURN bestProfit
PCode
2 / 3
suffixMax[n - 1] = prices[n - 1]

FOR i from n - 2 down to 0
    suffixMax[i] = max(prices[i], suffixMax[i + 1])

bestProfit = 0

FOR i from 0 to n - 1
    bestProfit = max(bestProfit, suffixMax[i] - prices[i])

RETURN bestProfit
PCode
3 / 3
minPrice = prices[0]
bestProfit = 0

FOR each price from left to right
    currentProfit = price - minPrice
    bestProfit = max(bestProfit, currentProfit)
    minPrice = min(minPrice, price)

RETURN bestProfit