Last updated on February 2nd, 2025 at 06:12 am

Here, we see a Best Time to Buy and Sell Stock with Transaction Fee LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array, Dynamic Programming, Greedy

Companies

Bloomberg, Facebook

Level of Question

Medium

Best Time to Buy and Sell Stock with Transaction Fee LeetCode Solution

1. Problem Statement

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 (i.e., you must sell the stock before you buy again).
The transaction fee is only charged once for each stock purchase and sale.

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

2. Coding Pattern Used in Solution

The coding pattern used in this code is Dynamic Programming (DP). Specifically, it is a State Transition DP approach. The problem is solved by maintaining two states (buy and sell) and updating them iteratively based on the current price and transaction fee.

3. Code Implementation in Different Languages

3.1 Best Time to Buy and Sell Stock with Transaction Fee C++

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int buy = INT_MIN;
        int sell = 0;
        for (int price : prices) {
            buy = max(buy, sell - price);
            sell = max(sell, buy + price - fee);
        }
        return sell;
    }
};

3.2 Best Time to Buy and Sell Stock with Transaction Fee Java

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int buy = Integer.MIN_VALUE;
        int sell = 0;
        for (int price : prices) {
            buy = Math.max(buy, sell - price);
            sell = Math.max(sell, buy + price - fee);
        }
        return sell;        
    }
}

3.3 Best Time to Buy and Sell Stock with Transaction Fee JavaScript

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

3.4 Best Time to Buy and Sell Stock with Transaction Fee Python

class Solution(object):
    def maxProfit(self, prices, fee):
        buy = float('-inf')
        sell = 0
        for price in prices:
            buy = max(buy, sell - price)
            sell = max(sell, buy + price - fee)
        return sell

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(1)
Java	O(n)	O(1)
JavaScript	O(n)	O(1)
Python	O(n)	O(1)

Where n is the number of elements in the prices array.

The code uses Dynamic Programming with two states (buy and sell) to optimize the solution.
It avoids using additional arrays or data structures, making it a space-efficient solution.
The logic is based on maximizing profit at each step by considering whether to buy or sell at the current price.