DSAPrep
EasySliding Window

Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the i-th day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6 - 1 = 5.

Example 2

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: Prices only fall, so no transaction is done and max profit = 0.

Constraints

  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^4
View original on LeetCode ↗

Brute Force

Time O(n²)Space O(1)

Try every pair of buy day i and sell day j > i, and keep the best prices[j] - prices[i]. Correct, but it recomputes the same subtractions over and over.

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        best = 0
        n = len(prices)
        for i in range(n):
            for j in range(i + 1, n):
                best = max(best, prices[j] - prices[i])
        return best

O(n²) pairs checked — too slow once n approaches 10^5.

One Pass (Track Minimum)

OptimalTime O(n)Space O(1)

The best sell day is always paired with the lowest price seen so far to its left — there’s never a reason to buy at a higher earlier price. So walk once, tracking the minimum price seen and the best profit achievable by selling today.

class Solution:
    def maxProfit(self, 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
day
7
0
1
1
5
2
3
3
6
4
4
5
minPrice = 7best = 0
1 / 6
seenresultcurrent

price=7. minPrice=7 (first day), profit today = 0.

Why it’s correct: at each day, the only decision that matters is “what’s the cheapest I could have bought for by now?” — everything else is dominated. Complexity: single pass, constant extra space → O(n) time, O(1) space, and this is optimal since you must look at every price at least once.