Best Time to Buy and Sell Stock

Problem

You are given an array prices where prices[i] is the price of a given stock on the ith 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.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

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

Solution

Approach: Single Pass with Minimum Tracking

The key insight is that we want to buy at the lowest price and sell at the highest price after that. We can track the minimum price seen so far as we iterate through the array, and calculate the profit if we were to sell at the current price.

We maintain two variables:

min_price: the lowest price we’ve seen so far (best day to buy)
max_profit: the maximum profit we can achieve

For each price, we:

Update max_profit if selling at the current price gives us a better profit
Update min_price if the current price is lower than our tracked minimum

Implementation

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float('inf')
        max_profit = 0

        for price in prices:
            # Update minimum price seen so far
            min_price = min(min_price, price)
            # Calculate profit if we sell at current price
            profit = price - min_price
            # Update maximum profit
            max_profit = max(max_profit, profit)

        return max_profit

Alternative (Two Pointers):

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        left = 0  # Buy
        right = 1  # Sell
        max_profit = 0

        while right < len(prices):
            # Profitable transaction
            if prices[left] < prices[right]:
                profit = prices[right] - prices[left]
                max_profit = max(max_profit, profit)
            else:
                # Found a lower price to buy at
                left = right
            right += 1

        return max_profit

Complexity Analysis

Time Complexity: O(n), where n is the length of the prices array. We make a single pass through the array.
Space Complexity: O(1), we only use a constant amount of extra space.

Key Insights

One Pass Solution: We don’t need to check all pairs of buy/sell days. By tracking the minimum price seen so far, we can calculate the best profit in a single pass.
Sliding Window Concept: This is a sliding window problem where we maintain the minimum on the left and check each potential selling point on the right.
Greedy Approach: At each step, we greedily update our minimum buy price and maximum profit. This works because we only care about the global maximum profit, not the specific days.
No Negative Profits: If no profitable transaction exists, our max_profit stays at 0, which is the correct answer (we just don’t make any transaction).