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 Sam K., 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

More DP 1D practice problems

See all DP 1D problems →