Coding Interview PatternsBest Time to Buy and Sell Stock
EasyGreedy Techniques

Best Time to Buy and Sell Stock

Explanation & Solution

Practice Problem

Description

Given an array prices where prices[i] is the price of a given stock on the ith day, find the maximum profit you can achieve by choosing a single day to buy and a single later day to sell.

Return the maximum profit. If no profit can be made, return 0.

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

Output: 5

Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6 - 1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Constraints

  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^4

Approach

Greedy Techniques pattern

1. Initialize Tracking Variables

  • Set minPrice to Infinity so that any price in the array will be smaller.
  • Set maxProfit to 0 since the worst case is no transaction (profit of 0).

2. Iterate Through Prices

  • Walk through the array from left to right, examining each price exactly once.
  • For each price, there are two possibilities: it could be a new minimum buy price, or it could yield a new maximum profit when paired with the current minimum.

3. Update the Minimum Price

  • If the current price is lower than minPrice, update minPrice to the current price.
  • This tracks the cheapest day to buy so far.

4. Update the Maximum Profit

  • Otherwise, compute the profit as prices[i] - minPrice.
  • If this profit exceeds maxProfit, update maxProfit.
  • This ensures we always consider selling at the current price after buying at the lowest price seen so far.

5. Return the Result

  • After scanning all prices, maxProfit holds the best possible profit from a single buy-sell transaction.
  • If prices only decrease, maxProfit remains 0.

Key Insight

  • The key observation is that the maximum profit on any given day is determined by the minimum price that occurred before it. By tracking the running minimum and comparing each day's potential profit against the best seen so far, we solve the problem in one pass without needing nested loops.
Time
O(n)a single pass through the array.
Space
O(1)only two variables are maintained.

Visualization

Input:
[7, 1, 5, 3, 6, 4]
701152336445
—

Press ▶ or use ← → to step through

Pointer iPointer jProcessedDone
7 steps

Solution Code

Previous
Jump Game II
Next
Best Time to Buy and Sell Stock II