Best Time to Buy and Sell Stock with Transaction Fee

Q: What is the time complexity of Best Time to Buy and Sell Stock with Transaction Fee?

O(n). Each day and holding state pair is computed once and cached, resulting in 2*n states and O(1) work per state.

Q: What pattern does Best Time to Buy and Sell Stock with Transaction Fee use?

The Pattern: Dynamic Programming (State Machine) The Heuristic: Model the problem as a state machine with states representing holding or not holding stock; at each step, choose the action (buy, sell, or hold) that maximizes profit while accounting for transaction fees, and use memoization to avoid redundant calculations.

Medium Dynamic Programming

Problem

Given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee, return the maximum profit you can achieve by completing as many transactions as you like, paying the fee for each transaction. You may not hold more than one share of the stock at a time.

1 ≤ prices.length ≤ 5 * 10⁴
1 ≤ prices[i] ≤ 5 * 10⁴
0 ≤ fee ≤ 5 * 10⁴

Example

Input: prices = [1, 3, 2, 8, 4, 9], fee = 2

Output: 8

The algorithm explores decisions day by day, tracking whether it currently holds stock. On day 0, it can buy at price 1 (holding = True). On day 3, it sells at price 8, paying fee 2, netting 8 - 2 - 1 = 5 profit. Then it buys again at day 4 price 4 and sells at day 5 price 9, netting 9 - 2 - 4 = 3 profit. Total profit is 5 + 3 = 8. The key is deciding at each day whether to buy, sell, or hold, considering the fee cost and future opportunities.

Approach

Straightforward Solution

A brute-force approach tries all buy/sell sequences, leading to exponential time complexity due to combinatorial explosion of transaction sequences.

Core Observation

At any day, the maximum profit depends on whether the stock is currently held or not. The decision to buy or sell affects future profits and must account for the transaction fee, which reduces the net gain from selling.

Path to Optimal

Preview

Recognizing the problem as a sequence of decisions with overlapping subproblems and optimal substructure suggests Dynamic Programming. The key insight is to model the problem as a state machine with two states per day: holding stock or not holding stock…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a top-down DP with memoization on states (day, holding_stock). For each day, compute the max profit by either skipping the day or performing a buy/sell action depending on the holding state…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each day and holding state pair is computed once and cached, resulting in 2*n states and O(1) work per state.

Space

O(n)

Memoization cache stores results for each day and holding state, totaling O(n) auxiliary space. The recursion stack depth is also O(n).

Pattern Spotlight

Dynamic Programming (State Machine)

Model the problem as a state machine with states representing holding or not holding stock; at each step, choose the action (buy, sell, or hold) that maximizes profit while accounting for transaction fees, and use memoization to avoid redundant calculations.

Solution

Python

1from functools import cache
2
3class Solution:
4    def maxProfit(self, prices: List[int], fee: int) -> int:
5        @cache
6        def dp(day, holding_stock):
7            if day >= len(prices):
8                return 0
9
10            max_profit = dp(day + 1, holding_stock)
11
12            if holding_stock:
13                max_profit = max(max_profit, prices[day] - fee + dp(day + 1, 0))
14            else:
15                max_profit = max(max_profit, -prices[day] + dp(day + 1, 1))
16
17            return max_profit
18
19        return dp(0, 0)

Step-by-Step Solution

Recursively Explore Profit States with Memoization

5@cache
6def dp(day, holding_stock):
  if day >= len(prices):
      return 0
  max_profit = dp(day + 1, holding_stock)
  if holding_stock:
      max_profit = max(max_profit, prices[day] - fee + dp(day + 1, 0))
  else:
      max_profit = max(max_profit, -prices[day] + dp(day + 1, 1))
  return max_profit

Objective

To compute the maximum profit from a given day and holding state by recursively deciding to hold, buy, or sell.

Key Insight

The problem breaks down into two states per day: holding stock or not. For each state, the algorithm compares the profit of skipping the day versus performing the allowed action (buy if not holding, sell if holding). Memoization ensures each state is computed once, preventing exponential recomputation and enabling efficient linear-time solution.

Interview Quick-Check

Core Logic

The DP function models two states per day (holding or not) and chooses the maximum profit between skipping or performing a buy/sell action, incorporating the transaction fee on selling.

State & Boundaries

The base case returns 0 profit when the day index exceeds the last day, ensuring recursion termination.

Common Pitfalls & Bugs

Applying the fee on buying instead of selling or forgetting to memoize states can lead to incorrect results or exponential time.

Complexity

Memoization reduces the exponential recursion tree to O(n) states, each computed once.

Return Final Maximum Profit Starting Without Stock

To initiate the DP recursion from day 0 with no stock held and return the maximum achievable profit.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 13 Critical

max_profit = max(max_profit, prices[day] - fee + dp(day + 1, 0))

Calculate max profit by either skipping or selling stock today, accounting for the fee.

Selling stock realizes profit equal to the current price minus the fee, transitioning to not holding state; comparing with skipping ensures the optimal choice is selected.

Line 7 Critical

if day >= len(prices):

Check if the current day exceeds the last day and return 0 profit if so.

This base case terminates recursion, ensuring that no further profit can be made beyond the last day.

Line 15 Critical

max_profit = max(max_profit, -prices[day] + dp(day + 1, 1))

Calculate max profit by either skipping or buying stock today.

Buying stock costs the current price (negative profit) and transitions to holding state; comparing with skipping ensures the best decision is chosen.

Full line-by-line criticality + rationale for all 11 lines available on Pro.

Test Your Understanding

Why does the transaction fee only apply when selling and not when buying?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Best Time to Buy and Sell Stock with Transaction Fee from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Best Time to Buy and Sell Stock with Transaction Fee drill

or drill a free problem

1	`from functools import cache`
2
3	`class Solution:`
4	`def maxProfit(self, prices: List[int], fee: int) -> int:`
5	`@cache`
6	`def dp(day, holding_stock):`
7	`if day >= len(prices):`
8	`return 0`
9
10	`max_profit = dp(day + 1, holding_stock)`
11
12	`if holding_stock:`
13	`max_profit = max(max_profit, prices[day] - fee + dp(day + 1, 0))`
14	`else:`
15	`max_profit = max(max_profit, -prices[day] + dp(day + 1, 1))`
16
17	`return max_profit`
18
19	`return dp(0, 0)`

5	`@cache`
6	`def dp(day, holding_stock):`
7	`if day >= len(prices):`
8	`return 0`
10	`max_profit = dp(day + 1, holding_stock)`
12	`if holding_stock:`
13	`max_profit = max(max_profit, prices[day] - fee + dp(day + 1, 0))`
14	`else:`
15	`max_profit = max(max_profit, -prices[day] + dp(day + 1, 1))`
17	`return max_profit`