DSA problem

Best Time to Buy and Sell Stock with Transaction Fee

MediumState Machine DPPattern: State Machine DPtop600AmazonMicrosoftGoogleBloombergMeta

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 — you must sell the stock before you buy again.

Without the fee, the optimal strategy collapses to a greedy sum of every positive day-to-day delta. The fee changes the picture: tiny profitable runs may be net losers because the fee exceeds the gain. The trader needs to decide when a run is "worth completing" by paying the fee, which is naturally modeled as a two-state machine: cash means we currently hold no stock, and hold means we are currently holding one share.

The DP transitions on day i with price p are: cash updates to the better of itself or hold + p - fee (sell today, paying the fee); hold updates to the better of itself or cash - p (buy today). Note that the fee can be charged at either the buy or the sell side without changing optimality; charging at the sell is conventional and keeps hold from going artificially low.

The optimal implementation uses two rolling scalars and processes prices left to right in a single pass. Order matters lightly: if we update cash first using the old hold, then update hold using the now-fresh cash, we permit a same-day "sell then buy" which is correctly equivalent to "do nothing". Either way the algorithm is O(n) time and O(1) space, and the answer is the final cash value because we should never end the period still holding stock.

Examples

Example 1

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

Output: 8

Explanation: Buy on day 1 (price = 1), sell on day 4 (price = 8) for net 8 - 1 - 2 = 5. Buy on day 5 (price = 4), sell on day 6 (price = 9) for net 9 - 4 - 2 = 3. Total profit is 8.

Example 2

Input: prices = [1,3,7,5,10,3], fee = 3

Output: 6

Explanation: Buy on day 1 (price = 1), sell on day 5 (price = 10) for net 10 - 1 - 3 = 6. Smaller intermediate transactions cost too much in fees relative to their gain.

Example 3

Input: prices = [1,2,3,4,5,6], fee = 1

Output: 4

Explanation: Buy on day 1 (price = 1) and sell on day 6 (price = 6) for net 6 - 1 - 1 = 4. Repeated tiny transactions would each pay the fee and net less.

Constraints

1 <= prices.length <= 5 * 10^4
1 <= prices[i] < 5 * 10^4
0 <= fee < 5 * 10^4
You may not engage in multiple transactions simultaneously.

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

dynamic-programmingstate-machinearraygreedy

Browse all DSA problems