Best Time to Buy and Sell Stock with Transaction Fee

Medium
310.

Best Time to Buy and Sell Stock with Transaction Fee

Best Time to Buy and Sell Stock with Transaction Fee is a medium coding problem on arrays, dynamic programming and greedy, asked in Amazon, Google and Bloomberg interviews.

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

You may complete as many transactions as you like but may hold at most one share at a time. Return the maximum profit.

Example 1

Input
prices = [1,3,2,8,4,9], fee = 2
Output
8
Explanation
Buy at 1, sell at 8, buy at 4, sell at 9: (8-1-2) + (9-4-2) = 8.

Example 2

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

Example 3

Input
prices = [5], fee = 1
Output
0

Constraints

  • 1 <= prices.length <= 40
  • 0 <= prices[i] <= 1000
  • 0 <= fee <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} prices
 * @param {number} fee
 * @return {number}
 */
var maxProfit = function(prices, fee) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Best Time to Buy and Sell Stock with Transaction Fee Solution

Best Time to Buy and Sell Stock with Transaction Fee solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Best Time to Buy and Sell Stock with Transaction Fee is a medium coding problem on arrays, dynamic programming and greedy, asked in Amazon, Google and Bloomberg interviews.

Problem statement

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

You may complete as many transactions as you like but may hold at most one share at a time. Return the maximum profit.

Example 1

Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8
Explanation: Buy at 1, sell at 8, buy at 4, sell at 9: (8-1-2) + (9-4-2) = 8.

Example 2

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

Example 3

Input: prices = [5], fee = 1
Output: 0

Constraints

  • 1 <= prices.length <= 40
  • 0 <= prices[i] <= 1000
  • 0 <= fee <= 1000

Hints for Best Time to Buy and Sell Stock with Transaction Fee

  1. Hint 1

    Track two running values: the best profit while holding nothing (cash) and while holding a share (hold).

  2. Hint 2

    Selling pays the fee once — charge it on the sale so a buy is never double-counted.

  3. Hint 3

    Each day, both values can only improve, so a single left-to-right pass is enough.

How to solve Best Time to Buy and Sell Stock with Transaction Fee

Two running values: cash (best profit holding nothing) and hold (best profit holding a share). Charge the fee on the sale so each round trip pays exactly once.

Approach

  1. Start cash = 0, hold = -prices[0].
  2. For each later price: cash = max(cash, hold + price - fee); hold = max(hold, cash - price).
  3. Return cash.

Why it works

With at most one share, the state is binary and each day either keeps the state or switches it at the day's price; the two maxima are the optimal substructure. Using the updated cash for hold on the same day is safe because sell-then-buy on one day is never better than not trading.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Charging the fee on both buy and sell double-counts it.

Reference solution

Python

def maxProfit(prices, fee: int) -> int:
    cash = 0
    hold = -prices[0]
    for price in prices[1:]:
        cash = max(cash, hold + price - fee)
        hold = max(hold, cash - price)
    return cash

Java

public static int maxProfit(int[] prices, int fee) {
    int cash = 0, hold = -prices[0];
    for (int i = 1; i < prices.length; i++) {
        cash = Math.max(cash, hold + prices[i] - fee);
        hold = Math.max(hold, cash - prices[i]);
    }
    return cash;
}

C++

int maxProfit(vector<int>& prices, int fee) {
    int cash = 0, hold = -prices[0];
    for (size_t i = 1; i < prices.size(); i++) {
        cash = max(cash, hold + prices[i] - fee);
        hold = max(hold, cash - prices[i]);
    }
    return cash;
}

JavaScript

var maxProfit = function(prices, fee) {
    let cash = 0, hold = -prices[0];
    for (let i = 1; i < prices.length; i++) {
        cash = Math.max(cash, hold + prices[i] - fee);
        hold = Math.max(hold, cash - prices[i]);
    }
    return cash;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming