Best Time to Buy and Sell Stock III Leetcode Solution

Difficulty Level Hard
Frequently asked in Adobe Amazon
algorithms Array coding Dynamic Programming Interview interviewprep LeetCode LeetCodeSolutionsViews 4214

Problem statement

In the problem “Best Time to Buy and Sell Stock  III,” 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 at most two transactions.

Example

prices = [1,2,3,4,5]
4

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

First day: buy

Second day: rest

Third day: rest

Fourth day: rest

Fifth day: sell

Approach for Best Time to Buy and Sell Stock III Leetcode Solution

This problem is a harder version of Best Time to Buy and Sell Stock. So must solve the easy version of the problem before jumping into this problem.

In comparison to the easy version where we can do only one transaction here, we can do at most two transactions. which means either one transaction or two transactions in such a way that gives maximum profit.

The trickiest part of the problem is how to handle the second transaction. This problem can be converted into an easy version of this problem, once we change our perspective to see this problem.

let’s say we completed our first transaction with a profit of 200 Rs. (This part is the same as Best Time to Buy and Sell Stock). So after the first transaction, we have 200 Rs in our hand.

Now when we go to buy a stock of 500 Rs. We can think it like, although the price of the stock is 500 Rs. But for us, it is 300 Rs because we already have 200 Rs in our hands and we got it for free.  Now we will make the second transaction in such a way to maximize the net profit in the same way as we did in Best Time to Buy and Sell Stock problem.

The approach will be more clear from this example:

leetcode solution to Best Time to Buy and Sell Stock III

Implementation

Java code for Best Time to Buy and Sell Stock III

import java.util.Arrays; 
public class Tutorialcup {
    public static int maxProfit(int[] prices) {
  int firstSell = 0;
  int secondSell = 0;
  int firstBuy = Integer.MAX_VALUE;
  int secondBuy = Integer.MAX_VALUE;
  for(int i = 0; i < prices.length; i++) {
    int p = prices[i];
    firstBuy = Math.min(firstBuy, p);
    firstSell = Math.max(firstSell, p - firstBuy);
    secondBuy = Math.min(secondBuy, p - firstSell);
    secondSell = Math.max(secondSell, p - secondBuy);
  }
  
  return secondSell;
    }
  public static void main(String[] args) {
    int [] arr = {1,2,3,4,5}; 
    int ans=  maxProfit(arr);
    System.out.println(ans);
  }
}
4

C++ code for Best Time to Buy and Sell Stock III

#include <bits/stdc++.h> 
using namespace std; 
     int maxProfit(vector<int>& prices) {
  int firstSell = 0;//stores profit after one sell
  int secondSell = 0;//stores profit after two sell
  int firstBuy = INT_MAX;
  int secondBuy = INT_MAX;
  int n=prices.size();
        for(int i=0;i<n;i++)
        {
            firstBuy=min(firstBuy,prices[i]);
            firstSell=max(firstSell,prices[i]-firstBuy);
            secondBuy=min(secondBuy,prices[i]-firstSell);
            secondSell=max(secondSell,prices[i]-secondBuy); 
        }
        return secondSell;
    }
int main() 
{ 
 vector<int> arr = { 1,2,3,4,5 }; 
 cout<<maxProfit(arr)<<endl; 
 return 0;
}
4

Complexity Analysis of Best Time to Buy and Sell Stock III 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

The space complexity of the above code is O(1) because we using memory only to store the answer.

References

Translate »