Best Time to Buy and Sell Stock

Difficulty: Easy

Problem

Given an array prices where prices[i] is the price of a given stock on the ith day, find the maximum profit. You must buy before you sell.

Example

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.

Brute-force approach

Try every pair of buy and sell days to find maximum profit.

Steps

1. For each buy day i
2. Try every sell day j > i
3. Calculate profit = prices[j] - prices[i]
4. Track maximum profit

Time complexity: O(n²) · Space complexity: O(1)

Trade-offs

• Checking all pairs is slow
• Many pairs are clearly suboptimal
• Don't need to check all

Optimal approach

Key insight: Best profit at any day = today's price - minimum price seen before today.

Track minimum price seen so far. At each price, check if selling now gives better profit.

Steps

1. Track minimum price seen
2. At each price, update min if smaller
3. Calculate profit if selling today
4. Track maximum profit

Time complexity: O(n) · Space complexity: O(1)