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.
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.