Stock trading dynamic programming problems are a classic interview cluster. Every variant – one transaction, unlimited, at most k, cooldown, fee – fits the same state machine framework. Master the pattern once and you can derive any variant on the fly.
LC 121 – Best Time to Buy and Sell Stock (One Transaction)
One buy and one sell. Track the minimum price seen so far and compute max profit at each step.
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
Time: O(n). Space: O(1). No DP table needed – just two running variables.
LC 122 – Best Time to Buy and Sell Stock II (Unlimited Transactions)
Unlimited transactions but can only hold one share at a time. Greedy: sum every upward move.
def maxProfit(prices):
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i-1]:
profit += prices[i] - prices[i-1]
return profit
Equivalently modeled as a state machine with two states: held (holding stock) and cash (not holding):
def maxProfit(prices):
held = -prices[0]
cash = 0
for price in prices[1:]:
held = max(held, cash - price) # buy or keep holding
cash = max(cash, held + price) # sell or stay in cash
return cash
Time: O(n). Space: O(1).
LC 123 – Best Time to Buy and Sell Stock III (At Most 2 Transactions)
At most 2 transactions. Model 4 states: after first buy, after first sell, after second buy, after second sell.
def maxProfit(prices):
hold1 = -prices[0] # max cash after first buy
sold1 = 0 # max cash after first sell
hold2 = -prices[0] # max cash after second buy
sold2 = 0 # max cash after second sell
for price in prices[1:]:
hold1 = max(hold1, -price) # buy first share
sold1 = max(sold1, hold1 + price) # sell first share
hold2 = max(hold2, sold1 - price) # buy second share
sold2 = max(sold2, hold2 + price) # sell second share
return sold2
The key insight: each state feeds into the next. Transitions flow one-way from left to right. Time: O(n). Space: O(1).
LC 188 – Best Time to Buy and Sell Stock IV (At Most k Transactions)
Generalize to k transactions. Use a 2D DP array: dp[j][0] = max cash with j transactions used and no stock held; dp[j][1] = max cash with j transactions used and stock held.
def maxProfit(k, prices):
n = len(prices)
if not prices or k == 0:
return 0
# If k >= n//2, unlimited transactions (LC 122 case)
if k >= n // 2:
profit = 0
for i in range(1, n):
if prices[i] > prices[i-1]:
profit += prices[i] - prices[i-1]
return profit
# dp[j][0] = max profit using at most j transactions, not holding stock
# dp[j][1] = max profit using at most j transactions, holding stock
dp = [[0, -prices[0]] for _ in range(k + 1)]
for price in prices[1:]:
for j in range(k, 0, -1):
dp[j][0] = max(dp[j][0], dp[j][1] + price) # sell
dp[j][1] = max(dp[j][1], dp[j-1][0] - price) # buy
return dp[k][0]
Time: O(n*k). Space: O(k). Iterate j in reverse to avoid using a transaction twice in one day.
LC 309 – Best Time to Buy and Sell Stock with Cooldown
Unlimited transactions but must wait one day after selling (cooldown). Three states: held (holding stock), sold (just sold – must cooldown), rest (in cooldown or doing nothing).
def maxProfit(prices):
held = -prices[0] # holding stock
sold = 0 # just sold today
rest = 0 # in rest/cooldown
for price in prices[1:]:
prev_held = held
prev_sold = sold
prev_rest = rest
held = max(prev_held, prev_rest - price) # keep holding or buy from rest
sold = prev_held + price # sell (must have been holding)
rest = max(prev_rest, prev_sold) # do nothing, or come off cooldown
return max(sold, rest)
Time: O(n). Space: O(1). The cooldown constraint just adds a one-step delay between sold and being able to buy again.
LC 714 – Best Time to Buy and Sell Stock with Transaction Fee
Unlimited transactions, pay fee on each sell. Deduct fee when selling.
def maxProfit(prices, fee):
held = -prices[0]
cash = 0
for price in prices[1:]:
held = max(held, cash - price)
cash = max(cash, held + price - fee) # pay fee on sell
return cash
Time: O(n). Space: O(1). Identical to LC 122 state machine with one extra term.
Unified State Machine Framework
Every stock problem is a state machine over combinations of (transactions_remaining, currently_holding):
- States: for each valid (txn_count, holding) pair, track max cash achievable.
- Transitions:
- Buy: move from not-holding to holding, subtract price, decrement remaining transactions (or count on buy, depending on convention).
- Sell: move from holding to not-holding, add price (minus fee if applicable), enter cooldown if required.
- Rest: stay in current state.
- Answer: max value across all not-holding states after processing all prices.
| Problem | Transactions | Extra Constraint | Time | Space |
|---|---|---|---|---|
| LC 121 | 1 | None | O(n) | O(1) |
| LC 122 | Unlimited | None | O(n) | O(1) |
| LC 123 | 2 | None | O(n) | O(1) |
| LC 188 | k | None | O(nk) | O(k) |
| LC 309 | Unlimited | 1-day cooldown | O(n) | O(1) |
| LC 714 | Unlimited | Transaction fee | O(n) | O(1) |
Interview Tips
- Start by identifying the constraints: how many transactions, any cooldown, any fee.
- Define states explicitly before writing code – name them (held, sold, rest) not dp[i][j][k].
- For at-most-k, recognize that k >= n/2 collapses to the unlimited case – handle it as a special case to avoid O(nk) when k is huge.
- Always derive state transitions verbally first: “From held, I can sell (go to sold) or do nothing (stay held).”
- The 4-variable approach for LC 123 (hold1, sold1, hold2, sold2) is the clearest code to write under pressure – no array indexing bugs.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is the state machine approach for stock trading DP problems?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Model the problem as states and transitions. For unlimited transactions (LC 122): two states per day – held (own a stock) and sold (do not own a stock). Transitions: held[i] = max(held[i-1], sold[i-1] – prices[i]) – either keep holding or buy today. sold[i] = max(sold[i-1], held[i-1] + prices[i]) – either stay sold or sell today. Answer: sold[n-1]. For cooldown (LC 309): three states – held, sold, rest. For k transactions (LC 188): dimension by transactions remaining. The state machine approach unifies all stock variants: identify the states, write the transitions, handle the boundary cases. You never need to "invent" a new DP for each variant.”}},{“@type”:”Question”,”name”:”How do you solve at most 2 transactions stock problem (LC 123)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Four state variables updated in one pass: buy1 = max profit after first buy (negative cost). sell1 = max profit after first sell. buy2 = max profit after second buy. sell2 = max profit after second sell. Transitions: buy1 = max(buy1, -price). sell1 = max(sell1, buy1 + price). buy2 = max(buy2, sell1 – price). sell2 = max(sell2, buy2 + price). Initialize buy1 = buy2 = -infinity, sell1 = sell2 = 0. The genius: sell1 profit feeds into buy2, naturally constraining the two transactions to be non-overlapping. Answer: sell2. O(n) time, O(1) space. Generalizes to k transactions with an array of size 2k.”}},{“@type”:”Question”,”name”:”How does the cooldown variant (LC 309) work?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”After selling, you must wait one day before buying again. Three states: held (own a stock), sold (just sold, in cooldown), rest (do not own, not in cooldown). Transitions: held[i] = max(held[i-1], rest[i-1] – price[i]) – keep holding or buy from rest state (not sold – in cooldown). sold[i] = held[i-1] + price[i] – sell the stock you held. rest[i] = max(rest[i-1], sold[i-1]) – either continue resting or come out of cooldown. Initial: held[0] = -prices[0], sold[0] = 0, rest[0] = 0. Answer: max(sold[n-1], rest[n-1]). The cooldown is enforced by: only the rest state (not the sold state) can transition to held.”}},{“@type”:”Question”,”name”:”What is the time complexity for each stock problem variant?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”LC 121 (one transaction): O(n) time, O(1) space – single pass tracking min price. LC 122 (unlimited transactions): O(n) time, O(1) space – state machine with 2 states. LC 123 (at most 2 transactions): O(n) time, O(1) space – 4 state variables. LC 188 (at most k transactions): O(n*k) time, O(k) space – 2D state machine, but if k >= n//2, equivalent to unlimited transactions (no real constraint). LC 309 (with cooldown): O(n) time, O(1) space – 3 state variables. LC 714 (with transaction fee): O(n) time, O(1) space – same as unlimited but deduct fee on each sell. The key optimization for all O(1) space variants: each state only depends on the previous day, so only keep the most recent values.”}},{“@type”:”Question”,”name”:”How do you solve the general k transactions case (LC 188) efficiently?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”dp[j][0] = max profit with j transactions remaining, not holding stock. dp[j][1] = max profit with j transactions remaining, holding stock. Transitions for each price: for j from k down to 1: dp[j][0] = max(dp[j][0], dp[j][1] + price) – sell. dp[j][1] = max(dp[j][1], dp[j-1][0] – price) – buy, using one transaction. Iterating j from k down to 1 (or using a copy of prev values) prevents using the same transaction twice in one day. Edge case: if k >= n//2 (more transactions allowed than possible non-overlapping trades), treat as unlimited – use the O(n) greedy. Answer: dp[k][0]. Time: O(n*k), space: O(k). For k=2, this reduces to the 4-state-variable solution.”}}]}
Robinhood interviews frequently test stock trading algorithms. See common questions for Robinhood interview: stock trading and financial DP problems.
Coinbase engineering tests trading algorithms and DP patterns. See patterns for Coinbase interview: trading algorithms and financial DP.
Meta coding interviews test state machine DP. See patterns for Meta interview: state machine DP and stock trading problems.