Best Time to Buy and Sell Stock with Transaction Fee
Source: Dev.to
Best Time to Buy and Sell Stock with Transaction Fee is a variation of the classic stock trading problem that introduces a realistic constraint: every time you sell a stock, you must pay a fixed transaction fee. You are given an array of prices, where each value represents the stock price on a given day, and an integer fee representing the cost of completing a transaction.
You can buy and sell the stock as many times as you want, but you can only hold one share at a time. You must sell before buying again. The goal is to maximize your total profit after accounting for the transaction fee on each sale.
This problem is popular in interviews because it looks like a greedy problem at first, but the transaction fee makes naive greedy strategies fail. It tests whether you can model decisions over time and manage state correctly.
Why simple greedy logic is not enough
In the version without fees, you can often make a profit by selling whenever the price goes up. With a transaction fee, that approach breaks down.
If you sell too often, the fee eats away at your profit. Small price increases may no longer be worth acting on. Sometimes it is better to hold the stock through minor dips and sell later, even if it means missing intermediate gains.
This means you cannot make decisions based on a single day. Each decision depends on previous choices, which makes this a dynamic programming problem rather than a purely greedy one.
The key idea behind the solution
The clean way to solve this problem is to track two states as you move through the price list:
- Holding – the maximum profit you can have while holding a stock at the end of the day.
- Not holding – the maximum profit you can have without holding a stock at the end of the day.
These two states fully describe everything that matters at any point in time. You do not need to remember the entire history of transactions, only the best outcome under each condition.
How the state transitions work
At the beginning, before any trading starts, your profit without holding a stock is zero. If you buy a stock on the first day, your profit becomes negative because you paid the price of the stock.
Each day, you decide whether to keep your current state or switch states.
-
If you are holding a stock:
- Keep holding, or
- Sell today, gaining today’s price minus the transaction fee.
Choose the option that yields higher profit.
-
If you are not holding a stock:
- Stay out of the market, or
- Buy today’s stock, reducing profit by the stock price.
Again, pick the better option.
These choices are made independently for each day, based on the previous day’s states.
Why the transaction fee is applied at selling time
A common interview question is why the fee is subtracted when selling rather than when buying.
Conceptually, a transaction is only completed when you sell. Buying opens a position, and selling closes it; the fee applies to that completed trade.
Mathematically, subtracting the fee at sell time keeps the logic clear and avoids double‑counting. The end result is the same as long as the fee is applied exactly once per buy–sell pair.
Why this approach works
The solution explores all valid sequences of actions without explicitly enumerating them. At each step, it considers the best possible profit for both holding and not‑holding states. No matter how many transactions you make, these two values are sufficient to describe your situation.
The approach naturally handles cases where it is better to wait through price fluctuations rather than selling immediately. The transaction fee is baked into the decision logic, so unprofitable trades are automatically avoided.
Performance in simple terms
- Time complexity: O(n) – the algorithm processes the price list once.
- Space complexity: O(1) – only a few variables are used to track the two states.
This is optimal and exactly what interviewers expect.
Want to explore more coding problem solutions? Check out the Squares of a Sorted Array and Number of Dice Rolls With Target Sum.