Skip to main content

714. Best Time to Buy and Sell Stock with Transaction Fee

medium

Unlimited transactions but each sale pays a flat fee. A two-state DP — hold vs cash — with the fee baked into the sell transition.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are 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. 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).

Constraints

  • 1 <= prices.length <= 5 * 10^4
  • 1 <= prices[i] < 5 * 10^4
  • 0 <= fee < 5 * 10^4

Examples

Example 1

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

Explanation: The maximum profit can be achieved by: Buying at prices[0] = 1. Selling at prices[3] = 8. Buying at prices[4] = 4. Selling at prices[5] = 9. The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Example 2

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Two states per day: holding a share or in cash.

Hint 2

Charge the fee at sell time. cash = max(cash, hold + price - fee); hold = max(hold, cash - price).

Hint 3

Update cash first then hold, or use the previous cash for hold to avoid double-counting one day.

Solution approach

Reveal approach

Two-state DP with rolling scalars. Let cash be the max profit when not holding and hold be the max profit when holding. Initialize cash = 0, hold = -prices[0]. For each price p: new_cash = max(cash, hold + p - fee) (either stay flat or sell paying the fee); new_hold = max(hold, cash - p) (stay holding or buy fresh from cash). Update both. The fee is subtracted exactly once per round-trip transaction by attaching it to the sell. Return cash at the end — holding at the close is never optimal. O(n) time, O(1) space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • dynamic-programming
  • state-machine

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Best Time to Buy and Sell Stock with Transaction Fee and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →