Best Time to Buy and Sell Stock — Single Transaction State Machine DP

Problem Statement#

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.

Constraints:

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

Example 1:

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

Example 2:

Input:  prices = [7, 6, 4, 3, 1]
Output: 0
Explanation: Prices only decrease — no profitable transaction is possible.

Example 3:

Input:  prices = [2, 4, 1]
Output: 2
Explanation: Buy on day 1 (price=2), sell on day 2 (price=4). Profit = 2.

Why This Problem Matters#

Best Time to Buy and Sell Stock (LC 121) is the gateway to the entire stock DP series. While the problem itself is solvable with a trivial one-pass approach, its real value is teaching the state machine DP framework that generalizes directly to:

• LC 122 (unlimited transactions)
• LC 123 (at most 2 transactions)
• LC 188 (at most k transactions)
• LC 309 (cooldown after selling)
• LC 714 (transaction fee)

Amazon, Google, Meta, and Microsoft ask these stock problems in series during the same interview. A candidate who only knows the greedy O(n) solution for LC 121 will fail LC 123 and beyond. A candidate who understands the state machine will solve all six variants with the same framework.

The Core Insight#

Greedy / linear scan approach: Track the minimum price seen so far. At each day, compute the profit if we sold today: price - min_so_far. Keep the running maximum of all such profits.

This is O(n) time and O(1) space — the simplest possible solution.

State machine DP formulation (the generalizable approach):

Define two states per day:

• hold: maximum profit achievable when you are holding a stock at the end of day i
• cash: maximum profit achievable when you are not holding a stock at the end of day i

Transitions:

• hold[i] = max(hold[i-1], -prices[i]) — either continue holding from yesterday, or buy today (for 1 transaction: buying costs prices[i], so profit = -prices[i])
• cash[i] = max(cash[i-1], hold[i-1] + prices[i]) — either rest from yesterday, or sell today

Base cases:

• hold[-1] = -infinity (haven't bought yet — represented as a large negative)
• cash[-1] = 0 (no transactions yet — profit is 0)

Answer: cash[n-1] (best profit when not holding at the end)

For the single-transaction case, hold[i] = max(hold[i-1], -prices[i]) ensures we never buy after already buying (no re-buying). This is equivalent to tracking the running minimum price.

Building the DP Solution#

Approach 1 — One-pass greedy (simplest):

def maxProfit(prices):
    min_price = float('inf')
    max_profit = 0
    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)
    return max_profit

Approach 2 — State machine DP (generalizable):

def maxProfit(prices):
    hold = float('-inf')  # haven't bought yet
    cash = 0              # no profit yet
    for price in prices:
        hold = max(hold, -price)          # buy today or keep holding
        cash = max(cash, hold + price)    # sell today or keep cash
    return cash

Both approaches are O(n) time, O(1) space. The state machine version extends directly to all stock variants.

Visual Dry Run#

Input: prices = [7, 1, 5, 3, 6, 4]

State machine trace:

Answer: cash = 5

Greedy trace (running minimum):

Both approaches give 5.

Optimized Solution#

Python#

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        # State machine: hold = best profit while holding a stock
        #                cash = best profit while not holding a stock
        hold = float('-inf')  # haven't bought yet — initialize to -infinity
        cash = 0              # no transaction yet — profit is 0
 
        for price in prices:
            # Either keep the current holding, or buy today
            hold = max(hold, -price)
            # Either keep the cash, or sell today (hold + price)
            cash = max(cash, hold + price)
 
        return cash

JavaScript#

var maxProfit = function(prices) {
    let hold = -Infinity;  // not yet holding any stock
    let cash = 0;          // no profit yet
 
    for (const price of prices) {
        hold = Math.max(hold, -price);         // buy or keep holding
        cash = Math.max(cash, hold + price);   // sell or keep cash
    }
 
    return cash;
};

Complexity Analysis#

Common Mistakes#

1. Selling before buying. When iterating left-to-right, the running minimum must be updated before computing the profit for the current day. In the greedy approach: update min_price first, then compute price - min_price.

2. Not returning 0 for all-decreasing prices. If prices are strictly decreasing, no profitable trade exists. Initialize max_profit = 0 (or cash = 0 in state machine) to handle this: if no trade is profitable, the answer is 0.

3. Trying to find the global minimum and maximum instead of the best pair. The global minimum might come after the global maximum. You must find the maximum prices[j] - prices[i] where i < j. Simply finding max(prices) - min(prices) is wrong when the minimum comes after the maximum.

4. Confusing the state machine initialization. hold = -infinity means "haven't bought yet — this state is currently unreachable." Using hold = 0 would mean "bought for free," which is incorrect and inflates profits.

5. Off-by-one: returning hold instead of cash. The answer is the maximum profit while NOT holding stock. cash (or not-hold state) is the correct return value. hold represents profit while still holding — always lower.

Interview Tips#

• Present both approaches: "The simplest is tracking the running minimum — O(n) time, O(1) space. But I want to show the state machine formulation because it generalizes to unlimited transactions, k transactions, and cooldown."
• Draw the state machine: two nodes (Hold, Cash) with labeled transitions. This visual instantly impresses interviewers.
• Explain the hold initialization: "hold = -infinity represents the 'not yet bought' state — it's unreachable until we actually buy. Using hold = 0 would give us a free stock, which is wrong."
• Proactively connect to follow-ups: "For unlimited transactions, I just change -prices[i] to cash + (-prices[i]) in the hold update, allowing re-buying after selling."

Follow-up Questions#

Q: What if you can make unlimited transactions? (LC 122) Change hold = max(hold, -price) to hold = max(hold, cash - price). Now buying after selling is allowed — cash accumulates across transactions.

Q: What if you can make at most 2 transactions? (LC 123) Track 4 states: buy1, sell1, buy2, sell2. Each is a separate state machine variable updated each day.

Q: What if you can make at most k transactions? (LC 188) Use a 2D DP table: dp[k][0/1] — k transaction states times 2 hold/not-hold states. The transitions are the same as LC 123, generalized.

Q: What if there is a cooldown after selling? (LC 309) Add a cooldown state between sell and buy. The buy transition reads from cooldown (2 days ago), not from sell (1 day ago).

Q: What if there is a transaction fee? (LC 714) In the sell transition, subtract the fee: cash = max(cash, hold + price - fee).

Key Takeaways#

• The one-pass greedy (track running minimum) is the simplest O(n)/O(1) solution for single-transaction stock DP.
• The state machine formulation (hold/cash states) is the generalizable framework for all 6 stock variants.
• hold = -infinity initialization represents "haven't bought yet" — using 0 would simulate getting a free stock.
• The answer is always the cash (not-hold) state at the end — never the hold state.
• Mastering this state machine unlocks LC 122, 123, 188, 309, and 714 without learning six separate algorithms — just one framework with minor parameter changes.
• Amazon, Google, Meta, and Microsoft frequently present stock problems in series — starting with LC 121 and escalating to LC 123 or LC 309 in the same session.