Best Time to Buy and Sell Stock

Concept

LeetCode #121.
Problem: 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. If you cannot achieve any profit, return 0.

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

The Naive Approach ($O(N^2)$)

You could use nested for loops. The outer loop selects a day to Buy. The inner loop checks every single future day to Sell, and records the Math.max profit.
This compares every single combination, resulting in $O(N^2)$ time. This will trigger a Time Limit Exceeded error for massive arrays.

The Optimal Approach ($O(N)$)

This is a beautiful, intuitive One-Pass algorithm.

If you are a time traveler looking at the stock market left-to-right, your goal is to find the absolute Lowest Price possible to Buy.
If you buy at the lowest price, how do you find the max profit? You just check every single day after that, and calculate the profit (Current Price - Lowest Price).

1. Create a variable minPrice initialized to Infinity.
2. Create a variable maxProfit initialized to 0.
3. Loop through the array left-to-right.
4. If the current price is strictly smaller than minPrice, we found a new historical low! Update minPrice.
5. Otherwise, if we didn’t find a new low, what happens if we sold our stock today? Calculate Current Price - minPrice.
6. Does this sale beat our global maxProfit? If yes, update it!

Implementation

// Time Complexity: O(N) (One single pass)
// Space Complexity: O(1)

function maxProfit(prices: number[]): number {
    let minPrice = Infinity;
    let maxProfit = 0;

    for (let i = 0; i < prices.length; i++) {
        const currentPrice = prices[i];

        // Did we find a new absolute lowest price to buy?
        if (currentPrice < minPrice) {
            minPrice = currentPrice;
        } 
        // We didn't find a new low. What if we sold today?
        else {
            const potentialProfit = currentPrice - minPrice;
            
            // Did we beat the global high score?
            if (potentialProfit > maxProfit) {
                maxProfit = potentialProfit;
            }
        }
    }

    return maxProfit;
}

Best Time to Buy and Sell Stock II (Infinite Transactions)

LeetCode #122. Problem: You can buy and sell the stock as many times as you want (but you must sell the stock before you buy again). What is the maximum profit?

Input: prices = [7, 1, 5, 3, 6, 4]
Output: 7 (Buy at 1, sell at 5 = 4 profit. Buy at 3, sell at 6 = 3 profit. Total = 7).

This sounds infinitely more complex, but the mathematical solution is shockingly simple. It is a pure Greedy Algorithm.
If you look at a graph of the stock market, you want to capture every single upward slope!
If the price tomorrow is higher than the price today, you physically time-travel, buy it today, and sell it tomorrow! You do this for every single positive slope in the entire array, greedily accumulating the exact mathematical peak profit.

function maxProfitMultiple(prices: number[]): number {
    let totalProfit = 0;

    for (let i = 1; i < prices.length; i++) {
        // Is tomorrow's price higher than today's?
        if (prices[i] > prices[i - 1]) {
            // Instantly buy today and sell tomorrow! Add the margin to our total.
            totalProfit += prices[i] - prices[i - 1];
        }
    }

    return totalProfit;
}

Interview Questions

Q: In Stock I, a developer uses Kadane’s Algorithm (Maximum Subarray) to solve it. How is this possible?
A: This is a famous paradigm shift. If you have an array of raw prices [7, 1, 5, 3, 6, 4], you can transform it into an array of Daily Price Differences: [ (1-7), (5-1), (3-5)... ] -> [-6, 4, -2, 3, -2].
If you run Kadane’s Algorithm on this new array, it will find the contiguous subarray with the absolute largest sum! The maximum subarray of the differences is exactly identical to the maximum profit! (The algorithm we wrote above is fundamentally just a highly optimized derivative of this).

Q: Are there more versions of this problem?
A: Yes. Stock III (Maximum 2 transactions) and Stock IV (Maximum K transactions) introduce complex constraints. Because you cannot use the Infinite Greedy trick, you are forced to use a heavy 2D Dynamic Programming Matrix where dp[day][transactionNumber] tracks the optimal state machine of Buying vs Selling on specific days. They are notorious “Hard” problems.