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

Problem statement

In the problem “Best Time to Buy and Sell Stock with Transaction Fee,” we are given an array where each element in the array contains the price of the given stock on that day.

The definition of the transaction is buying one share of stock and selling that one share of stock.

Our task is to find the maximum profit under the following restrictions:

1. We can’t buy a new stock if we have not sold the previous stock. that is at a time we can have at most one stock.
2. We can do multiple transactions.
3. Every time we will do a transaction we need to pay transaction fees.
4. At a time we cannot buy more than one stock.

Example

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

8

Explanation: maximum profit that can be obtained is 8. Following is the transaction detail:

The approach of Best Time to Buy and Sell Stock with Transaction Fee Leetcode Solution

To solve this problem we need to think about how we can maximize the profit by buying and selling stock. These are ways to make a maximum profit:

1. We will buy the stock at the minimum price and sell at the maximum price.
2. As we need to pay a fee for each transaction so, we will sell the stock only when the selling price>cost price+fee.
3. In spite of looking for the best selling price, we will sell the stock when we will encounter selling price>cost price+fee. Then the cost price will become the cost price- fee.

Implementation

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

//function to find maximum profit
#include <bits/stdc++.h> 
using namespace std; 
    int Profit(vector<int>& prices, int fee) {
        int n = prices.size();
        int ans = 0;
        int mn = prices[0];
        for(int i=0;i<n;i++)
        {
         if (prices[i] < mn)
                mn = prices[i];
         if(prices[i] > mn + fee)
         {
              ans += prices[i] - fee - mn;
              mn = prices[i] - fee;
         }
            
        }
           return ans;  
    }

int main() 
{ 
 vector<int> arr = {1, 3, 2, 8, 4, 9}; 
 int fee=2;
 cout<<Profit(arr,fee)<<endl; 
 return 0;
}

8

Java code for Best Time to Buy and Sell Stock with Transaction Fee

import java.util.Arrays; 
public class Tutorialcup {
 public static  int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int ans = 0;
        int mn = prices[0];
        for(int i=0;i<n;i++)
        {
         if (prices[i] < mn)
                mn = prices[i];
         if(prices[i] > mn + fee)
         {
              ans += prices[i] - fee - mn;
              mn = prices[i] - fee;
         }
            
        }
           return ans;  
    }
  public static void main(String[] args) {
    int [] arr = {1, 3, 2, 8, 4, 9}; 
    int fee=2;
    int ans=  maxProfit(arr,fee);
    System.out.println(ans);
  }
}

8

Complexity Analysis of Best Time to Buy and Sell Stock with Transaction Fee Leetcode Solution

Time complexity

The time complexity of the above code is O(n) because we are traversing the price array only once. Here n is the length of the price array.

Space complexity

O(1) because we using memory only to store the answer.

References