DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Best Time to Buy and Sell Stock

easySliding window Must-do

Problem statement

You are given prices, where prices[i] is the price of one share on day i. You may make exactly one trade: buy on one day and sell on a later day.

Return the largest profit that trade can make. If every possible trade loses money or breaks even, return 0 (you simply don't trade).

Examples

Example 1

Input: prices = [8, 3, 6, 1, 5, 9, 2]

Output: 8

Explanation: Buy on day 3 at price 1 and sell on day 5 at price 9.

Example 2

Input: prices = [9, 7, 4, 2]

Output: 0

Explanation: The price only falls, so no trade makes money.

Hints

Approach

Fix the sell day instead of the buy day. If you sell on day j, the best buy day is simply the cheapest day before j. So one pass is enough: remember the lowest price so far, and at each day check what selling today would earn.

  1. Set lowest to the first price and best = 0.
  2. For each price: update best = max(best, price - lowest), then lowest = min(lowest, price).
  3. Return best.

Checking the profit before updating lowest guarantees the buy day is never after the sell day. (Doing it in the other order also works here, since buying and selling on the same day gives 0.)

ComplexityTime O(n)Space O(1)
Python
class Solution:
def maxProfit(self, prices: list[int]) -> int:
lowest = prices[0]
best = 0
for price in prices:
best = max(best, price - lowest) # sell today
lowest = min(lowest, price) # or remember a cheaper buy
return best

Follow-up questions

  • Allow unlimited trades (one share held at a time) and return the maximum total profit.
  • Return the buy and sell day indices as well as the profit.

Frequently asked questions

The maximum may come before the minimum. In [2, 10, 1, 4] that formula gives 9, but you can't sell at 10 after buying at 1. The real answer is 8 (buy at 2, sell at 10).

It can be read as one: the left edge is the cheapest day so far and the right edge is today. It is also the simplest form of "keep a running best while you scan", the same one-pass idea used for running minimums and maximums over metrics.

The pattern is "largest rise from an earlier low to a later high" in a time series. Replace prices with queue depth, memory use or latency samples and it answers "what was the biggest increase from a previous low point?" in one pass over the data.