Stock Buy and Sell Problems
These problems are very important for coding interviews in general.
This set contains a set of six problems of varying difficulty and a wide range of topics varying from greedy, dynamic programming, etc.
Best Time to Buy and Sell Stock
Best Time to Buy and Sell Stock II
Best Time to Buy and Sell Stock III
Best Time to Buy and Sell Stock IV
Best Time to Buy and Sell Stock with Cooldown
Best Time to Buy and Sell Stock with Transaction Fee
For each of these problems, we have several excellent posts all over the internet explaining how to approach it.
Here, we will discuss a most generalized solution using a Recurrence Relation applicable to all of these problems, and its usage to each of the six problems above.
So, now to approach these problems we must be familiar with the very basic operations of the stock market which we will be using in our solution.
- Portfolio- a portfolio is a collection of financial investments like stocks, bonds, etc. Whenever we buy a stock it gets added up to our portfolio.
Valid Transactions:-
Buy
Sell
Rest/Hold
- Note:- For these set of problems it is a constraint that only valid order for a genuine transaction is BSBSBS…. i.e. a stock can be sold only after it is bought and at the end when all the transactions have been completed then the total number of stocks at that moment in our portfolio would be zero. Let 0 denote sold state of the stock and 1 denote the bought state of the stock.
The Recurrence Relation:-
T[i][k][0] = max(T[i-1][k][0],T[i-1][k][1]+price)......... 1T[i][k][1] = max(T[i-1][k][1],T[i-1][k-1][0]-price)....... 2
Terms in the recurrence relation:-
The term T[i][k][0] denotes that at any i th time, k transactions have been done and 0 here signifies that after doing that k th transaction we have reached in the sold state(i.e. current state is the sold state). Similarly, we deduce the meaning for the term T[i][k][1] , T[i-1][k][1], T[i-1][k-1][0].
Explanation of the recurrence relation:-
Left Hand Side of the relations denotes the amount earned up-till i-th transaction to land in a sold state.
T[i][k][0] = max(rest, sell) ( for 1)
rest -> continue with the amount earned up till now without buying the stock before i.e. T[i-1][k][0]
sell -> perform the buy-sell operation and reach the state T[i][k][0] from the state at T[i-1][k][1] by earning a profit from that stock i.e. price of that stock.
T[i][k][1] = max(rest, buy) ( for 2)
rest -> continue with the amount earned up till now with a stock in my portfolio i.e. T[i-1][k][1]
buy -> perform the sell-buy operation and reach the state T[i-1][k][1] (buy state by performing a total of k-1 transactions) by paying an extra cost for that stock i.e. price of that stock.
Base Cases or Trivial Cases:-
1. T[-1][k][0] = 0
2. T[i][0][0] = 0
3. T[-1][k][1] = -Inf
4. T[i][0][1] = -InfExplanations:-
- T[-1][k][0] = 0 signifies the amount gained up till -1 th stock is sold ((i.e. market not open) with at most k transactions which for obvious reasons is 0 as the market is not open for any transaction till now so there can be no gain.
- T[i][0][0] = 0 signifies total amount gained up till i th stock with at most 0 transactions.
- T[-1][k][1] = -Inf signifies that the amount gained up till -1 th stock is sold ((i.e. market not open) with at most k transactions to reach in the bought state is -Inf.
- T[i][0][1] = -Inf signifies total amount gained up till i-th stock with at most 0 transactions to reach in state 1 that is bought state.
The last two cases are not possible in a conventional stock market so we assume that -Inf i.e. a large amount of money has to be paid in order to achieve these cases.
Applications to specific cases
The above-mentioned six stock buy sell problems are classified by the value of k, which is the maximum number of allowable transactions (the last two also have additional requirements such as “cool down” or “transaction fee”). We will apply the general solution to each of them in this article.
1. Best Time to Buy and Sell Stock
Given an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note:- You cannot sell a stock before you buy one.
Example:
Input: prices=[100,180,260,310,40,535,695]
Output: 655
Explanation: Buy on day 5 (price = 40) and sell on day 7 (price = 695), profit = 695–40 = 655.
Here, k = 1
For this case, we really have two unknown variables on each day: T[i][1][0] and T[i][1][1], and the recurrence relations can be reduced as:
T[i][1][0] = max(T[i-1][1][0], T[i-1][1][1] + prices[i])
T[i][1][1] = max(T[i-1][1][1], T[i-1][0][0] — prices[i]) = max(T[i-1][1][1], -prices[i])
Code in Java:- public int maxProfit(int[] prices) {
if(prices.length==0)
return 0;
int Ti0=0; // initially when no stock is to be bought denotes base case 2
int Ti1=-(int)1e9; // denotes base case 4
for(int ele: prices){
Ti0=Math.max(Ti0,Ti1+ele);
Ti1=Math.max(Ti1,0-ele);
}
return Ti0;
}
2. Best Time to Buy and Sell Stock- II
Given an array prices for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example:
Input: prices=[100,180,260,310,40,535,695]
Output: 865
Explanation: Buy on day 1(price = 100) and sell on day 4 (price = 310), profit = 310–100 = 210.
Then buy on day 5 (price = 40) and sell on day 7 (price = 695), profit = 695–40 = 655.
Total profit= 210+655 = 865
Here, k = +Inf
If k is positive infinity, then there isn’t really any difference between k and k — 1 (because both k and k-1 are infinite), which implies T[i-1][k-1][0] = T[i-1][k][0] and T[i-1][k-1][1] = T[i-1][k][1].
Therefore, we still have two unknown variables on each day: T[i][k][0] and T[i][k][1] with k = +Infinity, and the recurrence relations can be reduced as:
T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-1][k-1][0] — prices[i]) = max(T[i-1][k][1], T[i-1][k][0] — prices[i])
Code in Java:-
public int maxProfit(int[] prices) {
if(prices.length==0)
return 0;
int Ti0=0; // initially when no stock is to be bought denotes base case 2
int Ti1=-(int)1e9; // denotes base case 4
for(int price: prices){
Ti0=Math.max(Ti0,Ti1 + price);
Ti1=Math.max(Ti1,Ti0 - price);
}
return Ti0;
}3. Best Time to Buy and Sell Stock- III
Given an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example :
Input: prices =[100,180,260,310,40,535,695]
Output: 865
Explanation: Buy on day 1(price = 100) and sell on day 4 (price = 310), profit = 310–100 = 210.
Then buy on day 5 (price = 40) and sell on day 7 (price = 695), profit = 695–40 = 655.
Total profit= 210+655 = 865
Similar to the case where k = 1, except now we have four variables instead of two on each day: T[i][1][0], T[i][1][1], T[i][2][0], T[i][2][1], and the recurrence relations are:
T[i][2][0] = max(T[i-1][2][0], T[i-1][2][1] + prices[i])
T[i][2][1] = max(T[i-1][2][1], T[i-1][1][0] — prices[i])
T[i][1][0] = max(T[i-1][1][0], T[i-1][1][1] + prices[i])
T[i][1][1] = max(T[i-1][1][1], — prices[i])
Code for Java:-public int maxProfit(int[] prices) {
if(prices.length==0)
return 0;
int Ti10= 0;
int Ti11= -(int)1e9;
int Ti20= 0;
int Ti21= -(int)1e9;
for(int price: prices){
Ti20=Math.max(Ti20,Ti21+price);
Ti21=Math.max(Ti21,Ti10-price);
Ti10=Math.max(Ti10,Ti11+price);
Ti11=Math.max(Ti11,0 - price);
}
return Ti20;
}
3. Best Time to Buy and Sell Stock- IV
Given an integer array prices where prices[i] is the price of a given stock on the ith day.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note:- Notice that you may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example :
Input: k = 2, prices = [100,180,260,310,40,535,695]
Output: 865
Explanation: Buy on day 1(price = 100) and sell on day 4 (price = 310), profit = 310–100 = 210.
Then buy on day 5 (price = 40) and sell on day 7 (price = 695), profit = 695–40 = 655.
Total profit= 210+655 = 865
Here, k= arbitrary
This is the most generic variant of this problem. Each day we need to update all the maximum profits with different k values corresponding to 0 or 1 stocks in the portfolio at the end of the transaction. However, there is a minor optimization we can do if k exceeds some critical value, beyond which the maximum profit will no longer depend on the number of allowable transactions but instead will be bound by the number of available stocks (length of the prices array).
A profitable transaction takes a minimum of two days., the maximum number of profitable transactions is thus n/2 (integer division). After this, no possible profitable transaction, which implies the maximum profit will stay the same thereafter. Therefore the critical value of k is n/2. If the given k is no less than this value, i.e., k >= n/2, we can extend k to positive infinity and the problem is equivalent to problem 2.
The following is the O(kn) time and O(k) space solution. Without this optimization, the code will be giving TLE for a large k value.
Code in Java:- public int maxProfit(int k, int[] prices) {
if(prices.length==0)
return 0; if(k>=prices.length/2){ int Ti0= 0;// initially when no stock is to be bought
int Ti1= -(int)1e9;
for(int price: prices){
Ti0=Math.max(Ti0,Ti1 + price);
Ti1=Math.max(Ti1,Ti0 - price);
}
return Ti0;
} else{ int Tik0[]=new int[k+1];
int Tik1[]=new int[k+1];
Arrays.fill(Tik1,-(int)1e9); for(int price: prices){
for(int j=k;j>=0;j--){ Tik0[j]=Math.max(Tik0[j],Tik1[j]+price);
Tik1[j]=Math.max(Tik1[j],Tik0[j-1]-price);
}
}
return Tik0[k];
}
5. Best Time to Buy and Sell Stock with Cooldown
Given an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:
Input: prices = [100,180,260,310,40,535,695]
Output: 815
Explanation: transactions = [buy, rest, sell, cooldown, buy, rest, sell]
Here, k = +Inf but with a cooldown
This problem is very similar to problem 2 as the value of k is the same, but here the recurrence relations have to be modified to fulfill the condition of “cooldown” as follows:
T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-2][k][0] — prices[i])
If a stock has to be bought or sold on i-th day then we can buy it or sell it on (i-1) th day but on (i-2)th day.
Code in Java:- public int maxProfit(int[] prices) {
int Ti0= 0;
int Ti1= -(int)1e9;
int Ti2= 0;
for(int price: prices){
int temp=Ti0;
Ti0=Math.max(Ti0,Ti1+price);
Ti1=Math.max(Ti1,Ti2-price);
Ti2=temp;
}
return Ti0;
}
6. Best Time to Buy and Sell Stock with Transaction Fee
Given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee.
You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)
Return the maximum profit you can make.
Example :
Input: prices = [100,180,260,310,40,535,695], fee = 50
Output: 765
Explanation: Buy on day 1(price = 100) and sell on day 4 (price = 310), profit = 310–100 = 210.
Then buy on day 5 (price = 40) and sell on day 7 (price = 695), profit = 695–40 = 655.
Total profit= 210+655 = 865
Total Transaction Fee = 50+50= 100
Net profit = 865–100 = 765
Here, k = +Inf but with a transaction fee
This problem is very similar to problem 2 as the value of k is the same, but here the recurrence relations have to be modified to fulfill the condition of “transaction fee” as follows(considering selling as completion of one transaction, could be done alternatively in a similar manner):
T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-1][k][0] — prices[i] — fee)
Code in Java:-public int maxProfit(int[] prices, int fee) {
if(prices.length==0)
return 0;
int Ti0=0;
int Ti1= -(int)1e9;
for(int price: prices){
Ti0=Math.max(Ti0,Ti1+price-fee);//Considered selling as a completion of one transaction
Ti1=Math.max(Ti1,Ti0-price);
}
return Ti0;
}
The End! Happy Coding!!!
This article is based on an approach in the Leetcode discussion portal for the “Stock Buy and Sell Problems”. I am thankful to its author for sharing such a nice approach in the discussion portal.
