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.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Greedy
- Asked at: Amazon, Google, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 400 <= prices[i] <= 10000 <= fee <= 1000
Hints for Best Time to Buy and Sell Stock with Transaction Fee
Hint 1
Track two running values: the best profit while holding nothing (
cash) and while holding a share (hold).Hint 2
Selling pays the fee once — charge it on the sale so a buy is never double-counted.
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
- Start
cash = 0,hold = -prices[0]. - For each later price:
cash = max(cash, hold + price - fee);hold = max(hold, cash - price). - 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 cashJava
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