Best Time to Buy and Sell Stock: track min price and max profit

• Single-pass scan walks the price array once, maintaining two variables: the minimum price seen so far and the maximum profit achievable.
• Greedy logic updates the minimum price whenever a lower price appears, and computes the sell profit as currentPrice - minPrice each day.
• Buy-before-sell is guaranteed because the running minimum always comes from a day before or equal to the current day.
• Default to zero handles the case where prices only decline, since maxProfit is initialized to zero and never goes negative.
• Complexity is O(n) time and O(1) space, which is optimal for this problem.

What is the Best Time to Buy and Sell Stock problem?

You are given an array where each element represents the price of a stock on a given day. You are allowed to buy once and sell once, and you must buy before you sell. The goal is to find the maximum profit. If no profit is possible because prices only decline, you return zero.

For example, given prices [7, 1, 5, 3, 6, 4], the best strategy is to buy on day 2 at price 1 and sell on day 5 at price 6, for a profit of 5.

package com.bank.trading;

import java.math.BigDecimal;

/**
 * Finds the maximum profit from a single buy-sell transaction.
 * Uses BigDecimal for exact financial arithmetic.
 */
public class StockProfitCalculator {

    public static BigDecimal maxProfit(BigDecimal[] prices) {
        if (prices == null || prices.length < 2) {
            return BigDecimal.ZERO;
        }
        BigDecimal minPrice = prices[0];
        BigDecimal maxProfit = BigDecimal.ZERO;

        for (int i = 1; i < prices.length; i++) {
            if (prices[i].compareTo(minPrice) < 0) {
                minPrice = prices[i];
            } else {
                BigDecimal profit = prices[i].subtract(minPrice);
                if (profit.compareTo(maxProfit) > 0) {
                    maxProfit = profit;
                }
            }
        }
        return maxProfit;
    }

    public static void main(String[] args) {
        BigDecimal[] prices = {
            new BigDecimal("107.50"),
            new BigDecimal("101.00"),
            new BigDecimal("105.25"),
            new BigDecimal("103.00"),
            new BigDecimal("106.75"),
            new BigDecimal("104.00")
        };
        System.out.println("Max profit: " + maxProfit(prices));
    }
}

Max profit: 5.75

Why does this problem matter in interviews?

This is one of the most frequently asked interview questions because it tests whether you can optimize a brute-force O(n^2) solution down to O(n) using a running state variable. The brute force checks every pair of buy and sell days, while the optimal solution remembers the best buy price seen so far and only computes the sell profit for the current day.

In trading and portfolio management at banks, this logic is the foundation of single-trade profit analysis. A compliance system might need to flag the largest intra-day gain a trader could have captured.

// Brute force: O(n^2) - check every pair
public static BigDecimal maxProfitBrute(BigDecimal[] prices) {
    BigDecimal maxProfit = BigDecimal.ZERO;
    for (int buy = 0; buy < prices.length; buy++) {
        for (int sell = buy + 1; sell < prices.length; sell++) {
            BigDecimal profit = prices[sell].subtract(prices[buy]);
            if (profit.compareTo(maxProfit) > 0) {
                maxProfit = profit;
            }
        }
    }
    return maxProfit;
}
// This works but is too slow for large price histories

How does the single-pass algorithm work internally?

The algorithm initializes minPrice to the first day's price and maxProfit to zero. Starting from day 2, it processes each day in sequence.

For each day, two things happen:

1. If the current price is lower than minPrice, update minPrice. This day is a better buy candidate.
2. Otherwise, compute the profit of selling today as currentPrice - minPrice. If this exceeds maxProfit, update maxProfit.

Because minPrice always comes from a day before or on the current day, the buy-before-sell constraint is automatically satisfied. The scan processes each price exactly once, so the time is O(n) and the space is O(1).

// Step-by-step trace for prices [7, 1, 5, 3, 6, 4]
// Day 1: price=7, minPrice=7, maxProfit=0
// Day 2: price=1, 1<7 -> minPrice=1, maxProfit=0
// Day 3: price=5, profit=5-1=4 -> maxProfit=4
// Day 4: price=3, profit=3-1=2 -> maxProfit=4 (no update)
// Day 5: price=6, profit=6-1=5 -> maxProfit=5
// Day 6: price=4, profit=4-1=3 -> maxProfit=5 (no update)
// Answer: 5

How is this different from the multi-transaction variant?

The single-transaction problem allows one buy and one sell. The multi-transaction variant (Stock II) allows unlimited transactions but you cannot hold more than one share at a time. The approach is completely different.

| Aspect | Stock I (single transaction) | Stock II (multiple transactions) |
|---|---|---|
| Transactions | One buy, one sell | Unlimited buy-sell pairs |
| Approach | Track min price and max profit | Sum every positive day-to-day difference |
| Logic | maxProfit = max(maxProfit, price - minPrice) | profit += max(0, prices[i] - prices[i-1]) |
| Time | O(n) | O(n) |
| Space | O(1) | O(1) |

// Stock II: sum every positive day-to-day difference
public static BigDecimal maxProfitMultiple(BigDecimal[] prices) {
    BigDecimal totalProfit = BigDecimal.ZERO;
    for (int i = 1; i < prices.length; i++) {
        BigDecimal diff = prices[i].subtract(prices[i - 1]);
        if (diff.compareTo(BigDecimal.ZERO) > 0) {
            totalProfit = totalProfit.add(diff);
        }
    }
    return totalProfit;
}

What are the edge cases?

The important edge cases are:

• Declining prices: [5, 4, 3, 2, 1] has no profitable trade, so the answer is zero.
• All same prices: [3, 3, 3, 3] produces zero profit because selling at the same price yields nothing.
• Single element: an array with fewer than two prices has no buy-sell pair, so the answer is zero.
• Minimum at the end: [3, 2, 1] where the cheapest price is on the last day. No sell day follows it, so profit is zero.
• Maximum at the start: [10, 5, 3, 1] where the highest price is on the first day but you cannot sell before buying.

package com.bank.trading;

public class StockEdgeCases {
    public static void main(String[] args) {
        // Declining prices
        BigDecimal[] declining = {bd("5"), bd("4"), bd("3"), bd("2"), bd("1")};
        System.out.println("Declining: " + StockProfitCalculator.maxProfit(declining));

        // All same
        BigDecimal[] same = {bd("3"), bd("3"), bd("3")};
        System.out.println("Same: " + StockProfitCalculator.maxProfit(same));

        // Single element
        BigDecimal[] single = {bd("5")};
        System.out.println("Single: " + StockProfitCalculator.maxProfit(single));

        // Profit at the very end
        BigDecimal[] lateRise = {bd("10"), bd("3"), bd("2"), bd("1"), bd("15")};
        System.out.println("Late rise: " + StockProfitCalculator.maxProfit(lateRise));
    }

    private static BigDecimal bd(String val) {
        return new BigDecimal(val);
    }
}

Declining: 0
Same: 0
Single: 0
Late rise: 14

What are common mistakes?

The most common mistake is initializing minPrice to zero instead of the first element. If all prices are positive, a zero minimum makes the profit calculation wrong because you assume a buy price of zero that never existed.

// WRONG: initializing minPrice to zero
BigDecimal minPrice = BigDecimal.ZERO; // BUG: no day has price 0
BigDecimal maxProfit = BigDecimal.ZERO;
for (BigDecimal price : prices) {
    BigDecimal profit = price.subtract(minPrice);
    maxProfit = maxProfit.max(profit);
    minPrice = minPrice.min(price);
}
// For prices [3, 5], this reports profit 5 (5 - 0) instead of 2 (5 - 3)

// CORRECT: seed minPrice with the first element
BigDecimal minPrice = prices[0];
BigDecimal maxProfit = BigDecimal.ZERO;
for (int i = 1; i < prices.length; i++) {
    minPrice = minPrice.min(prices[i]);
    BigDecimal profit = prices[i].subtract(minPrice);
    maxProfit = maxProfit.max(profit);
}
// For prices [3, 5], this correctly reports profit 2

Another common mistake is allowing sells before buys by not maintaining the correct order in the scan.

What about the cooldown variant?

The cooldown variant (Stock with Cooldown) adds a rule: after selling, you must wait one day before buying again. This turns the problem into a state machine with three states: hold, sold, and rest.

// Stock with Cooldown: state machine approach
public static int maxProfitCooldown(int[] prices) {
    int n = prices.length;
    if (n < 2) return 0;

    int hold = -prices[0]; // holding a stock
    int sold = 0;          // just sold
    int rest = 0;          // resting (cooldown)

    for (int i = 1; i < n; i++) {
        int prevHold = hold;
        int prevSold = sold;
        int prevRest = rest;

        hold = Math.max(prevHold, prevRest - prices[i]);
        sold = prevHold + prices[i];
        rest = Math.max(prevRest, prevSold);
    }
    return Math.max(sold, rest);
}

Recognizing which variant you face is the first step to choosing the right technique.

What about the Kadane's algorithm connection?

The stock problem can be reframed as finding the maximum subarray sum of the day-to-day price differences. The difference array for [7, 1, 5, 3, 6, 4] is [-6, 4, -2, 3, -2]. The maximum subarray sum of this difference array is 4 + (-2) + 3 = 5, which matches the stock profit.

This connection shows that the stock problem and the maximum subarray problem are structurally the same.

// Kadane's on the difference array
public static int maxProfitKadane(int[] prices) {
    int maxProfit = 0;
    int currentSum = 0;
    for (int i = 1; i < prices.length; i++) {
        currentSum += prices[i] - prices[i - 1];
        if (currentSum < 0) currentSum = 0;
        maxProfit = Math.max(maxProfit, currentSum);
    }
    return maxProfit;
}
// For [7, 1, 5, 3, 6, 4], differences are [-6, 4, -2, 3, -2]
// Kadane's finds max subarray sum = 5 (from index 1 to 3)

What should a senior engineer know?

A senior engineer should know all the stock problem variants and how their approaches differ:

• Stock I: single transaction, track min price and max profit.
• Stock II: unlimited transactions, sum positive differences.
• Stock III: at most two transactions, use two forward/backward passes or DP with states.
• Stock IV: at most k transactions, generalized DP.
• Stock with Cooldown: state machine with hold, sold, rest.
• Stock with Transaction Fee: similar to Stock II but subtract the fee on each sell.

In production trading systems, these algorithms run on streaming price data. The single-pass nature of Stock I makes it suitable for real-time computation where you cannot afford to store and revisit the entire price history.

What are common interview follow-up questions?

Interviewers often ask:

• Can you solve this with Kadane's algorithm? Yes, by transforming to a difference array.
• What if you could short-sell? The problem becomes finding the maximum loss, which is the same algorithm with signs flipped.
• What if prices can be negative? The algorithm still works because it tracks the minimum and computes differences.
• How would you return the buy and sell days, not just the profit? Track the indices where minPrice and maxProfit are updated.