Log inSign up
mediumLeetCodeNot Started

Best Time to Buy and Sell Stock with Transaction Fee

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the i-th day, and an integer fee representing a transaction fee.

Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.

Note: - You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again). - You only pay the fee once per complete transaction (either when buying or selling).

### Example 1 - Input: prices = [1, 3, 2, 8, 4, 9], fee = 2 - Output: 8 - Explanation: Maximum profit is achieved by: - Buying at prices[0] = 1 - Selling at prices[3] = 8 -> profit = 8 - 1 - 2 = 5 - Buying at prices[4] = 4 - Selling at prices[5] = 9 -> profit = 9 - 4 - 2 = 3 - Total profit is 5 + 3 = 8.

### Example 2 - Input: prices = [1, 3, 7, 5, 10, 3], fee = 3 - Output: 6 - Explanation: Buy at 1, sell at 10: 10 - 1 - 3 = 6.

Constraints:

  • 1 <= prices.length <= 5 * 104
  • 1 <= prices[i] <= 5 * 104
  • 0 <= fee <= 5 * 104

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why naive greedy slope accumulation fails in the presence of transaction friction.
  • Adapt the 2-state stock DP paradigm to incorporate constant fixed penalties.
  • Ensure O(1) auxiliary space execution.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Stock price array with a fixed transaction fee deducted per round trip.
  • Unlimited transactions allowed.

Algorithmic Decision Tree:

  • Extend Stock II by subtracting fee during either the buy or sell transition.
  • Greedy slope summation fails because minor bumps don't cover the transaction fee.

Connected Patterns:

Best Time to Buy and Sell Stock IIBest Time to Buy and Sell Stock with Cooldown

1. Recursive Branching with Fee Penalty

Intuition

Branch at each day into buying, selling, or doing nothing, accounting for the fee whenever a transaction occurs.

Algorithm

  1. Define dfs(day, holding).
  2. If day == prices.length, return 0.
  3. If holding: choice 1 is sell prices[day] - fee + dfs(day + 1, false); choice 2 is hold dfs(day + 1, true).
  4. If not holding: choice 1 is buy -prices[day] + dfs(day + 1, true); choice 2 is skip dfs(day + 1, false).
  5. Return max of choices.

Recursive Decision Tree with Fee Deduction

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Root of decision tree
Visual state
Values and pointers at this exact step
table
S
buy
0
day0
price1
fee2
Variables at this step
day
0
price
1
fee
2
Check / comparison
Day 0: price = 1. Choice: Buy or Skip
Decision / next transition
Branch 1: Buy (spend 1, hold stock). Branch 2: Skip (cash 0).
Why this step matters

Root of decision tree.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int dfsFee(int day, bool holding, int fee, const vector<int>& prices) {
8 if (day == (int)prices.size()) return 0;
9 if (holding) {
10 int sell = prices[day] - fee + dfsFee(day + 1, false, fee, prices);
11 int keep = dfsFee(day + 1, true, fee, prices);
12 return max(sell, keep);
13 } else {
14 int buy = -prices[day] + dfsFee(day + 1, true, fee, prices);
15 int skip = dfsFee(day + 1, false, fee, prices);
16 return max(buy, skip);
17 }
18}
19
20int maxProfitFeeRec(const vector<int>& prices, int fee) {
21 return dfsFee(0, false, fee, prices);
22}
23
24int main() {
25 vector<int> prices = {1, 3, 2, 8, 4, 9};
26 int fee = 2;
27 cout << "Max Profit (Recursive): " << maxProfitFeeRec(prices, fee) << endl;
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(n) call stack

2. 2D Tabulation DP

Intuition

Construct a 2D table dp[n][2] where dp[i][0] is cash without stock and dp[i][1] is balance holding stock.

Algorithm

  1. dp[0][0] = 0, dp[0][1] = -prices[0] - fee.
  2. For i = 1 to n - 1:
  3. dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
  4. dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee)
  5. Return dp[n - 1][0].

2D Dynamic Programming (Cash vs Hold)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Buying stock on day 0 reduces balance by price 1
Visual state
Values and pointers at this exact step
table
S
cash:0, hold:-1
0
day0
cash0
hold-1
Variables at this step
day
0
cash
0
hold
-1
Check / comparison
Base: dp[0][0] = 0 (cash), dp[0][1] = -prices[0] = -1 (hold)
Decision / next transition
Initialize day 0 DP states.
Why this step matters

Buying stock on day 0 reduces balance by price 1.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int maxProfitFee2D(const vector<int>& prices, int fee) {
8 int n = prices.size();
9 if (n <= 1) return 0;
10
11 vector<vector<int>> dp(n, vector<int>(2, 0));
12 dp[0][0] = 0;
13 dp[0][1] = -prices[0] - fee;
14
15 for (int i = 1; i < n; i++) {
16 dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
17 dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee);
18 }
19 return dp[n - 1][0];
20}
21
22int main() {
23 vector<int> prices = {1, 3, 2, 8, 4, 9};
24 int fee = 2;
25 cout << "Max Profit (2D DP): " << maxProfitFee2D(prices, fee) << endl;
26 return 0;
27}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(n) for 2D table

3. O(1) Space State Machine DP

Intuition

Maintain two scalars cash and hold in a single forward pass, updating in O(1) space.

Algorithm

  1. cash = 0, hold = -prices[0] - fee.
  2. For each price in prices from index 1:
  3. cash = max(cash, hold + price)
  4. hold = max(hold, cash - price - fee)
  5. Return cash.

Two-Register State Machine (O(N) Time, O(1) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
O(1) space state machine representation
Visual state
Values and pointers at this exact step
table
S
cash=0, hold=-1
0
cash0
hold-1
Variables at this step
cash
0
hold
-1
Check / comparison
Initialize: cash = 0, hold = -prices[0] = -1
Decision / next transition
Starting with 0 cash and 1 bought stock.
Why this step matters

O(1) space state machine representation.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int maxProfitFeeOptimal(const vector<int>& prices, int fee) {
8 if (prices.empty()) return 0;
9 int cash = 0;
10 int hold = -prices[0] - fee;
11
12 for (size_t i = 1; i < prices.size(); i++) {
13 cash = max(cash, hold + prices[i]);
14 hold = max(hold, cash - prices[i] - fee);
15 }
16 return cash;
17}
18
19int main() {
20 vector<int> prices = {1, 3, 2, 8, 4, 9};
21 int fee = 2;
22 cout << "Max Profit (Optimal O(1) Space): " << maxProfitFeeOptimal(prices, fee) << endl;
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(1) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive TreeO(2^n)O(n)Exhaustive branching over buy/sell choices.Repeated state calls
2.2D TabulationO(n)O(n)Fill table tracking cash and hold across n days.Array allocations
3.Rolling 2-State ScalarsOptimalO(n)O(1)Update cash and hold variables in place with fee applied on buy.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Subtracting the fee BOTH on buy AND on sell (double charging).

Pitfall 2:

Using greedy slope accumulation without considering that small dips (< fee) should not trigger a sell-and-rebuy.

Crucial Edge Cases to Validate:

  • fee is greater than any potential price gain: Output is 0.
  • fee is 0: Identical to Stock II.
  • Single day: Output is 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Point out that this problem smoothly unifies Stock II (where fee = 0) into a parameterized state machine.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Does it matter mathematically whether we subtract the fee when buying versus when selling?

Back to DSA Sheet