Leetcode Stocks Pattern
In competitive programming, there are bunch of problems related to buying and selling stocks. Most of these problems have the same setup i.e.
You are given a list of prices for a sequence of days and some threshold on number of transactions you can make and your goal is to determine the maximum profit you can make.
I found one blog post on leetcode explaining the pattern to solve the problem which I will link in references section.
Let’s jump on to understanding the problem setup. As we need to make the decisions sequentially most of these problems have optimal substructure and hence can be solved with recursion.
Problems involving recursion wants us to solve the recurrence relation. We need to solve the recurrence to connect the past decisions to the current decision we want to make.
So let’s start by digging in what we need to keep track of:-
We need to track the current day we want to make the decision for, we need to keep track of the fact do we still have stocks left or not and to track the number of transactions made so far.
i.e. Table[Day, MaxTransactionsMadeSoFar, DoWeHaveAnyStocksLeft]
Actions we can take everyday
- Rest: Don’t do anything today.
- Buy: Buy stock today.
- Sell: Sell stock today. only condition is you should have stocks in-hand before selling it.
So let’s define some notation to proceed further.
T[i, j, false]: Defines the profit we made till day-i after making atmost j transaction and we have no stocks left to sell.
T[i, j, true]: Defines the profit we made till day-i after making atmost j transactions and we have stocks left to be sold.
Our goal is to find the entry T[n, k, false] i.e. how much profit we made after n days and doing atmost k transaction and we had no stocks left to sell where n and k is given by user.
Solving the recurrence
Base cases: There are 4 base cases.
- Make some profit by doing 0 transactions and have no stocks left i..e. T[i, 0, false] = 0 because you can not make any profit by doing 0 transactions.
- Make some profit by doing 0 transactions and have some stocks left to sell i.e. T[i, 0, true]=-Infinity because if you won’t do any transaction you can’t have any stocks left in your pocket.
3. Make some profit before starting day itself and have no stocks left i.e. T[0, j, false] =0 because you can’t make any profit before first day.
4. Make some profit before starting day itself and have some stocks left i.e. T[0, j, true]=-Infinity because we can’t save any stocks as there were no stocks left on day-0.
Inductive cases:
Case-1: If We don’t want to keep the stocks today then there are 2 cases to deal with. Either We will rest today i.e. ask for profit made till day i-1 with those many transactions or We will sell some stocks today i.e. ask for profit made till day i-1 by keeping some stocks after atmost k transactions and sell those at today’s price.
T[day=i, MaxTransaction=j, KeepStocks=False]=max(restToday, sellToday)
i.e. T[i, j, false] = max(T[i-1, j, false], t[i-1, j, true]+StockPrice[i])
Case-2: If we want to keep the stocks in-hand today then there are again 2 cases to deal with. Either we will rest today i.e. ask for profit made till day i-1 by atmost k transactions and keeping some stocks or the profit made till i-1 days with k-1 transactions( as we will make kth transaction of buying stocks now) and keeping some stocks and make the kth transaction by buying stocks now.
T[day=i, MaxTransaction=j, KeepStocks=True]=max(restToday, buyToday)
i.e. T[i, j, true] = max(T[i-1, j, true], T[i-1, j-1, false]-StockPrice[i])
Applications
Leetcode-121: Given an array of prices and you can make atmost one transaction.
Solution: Problem setup clearly dictates that j=1 because number of transactions will be atmost one.
Let’s start with recurrence.

As we can see in the above recurrence, index j for maxTransaction is useless so we can get rid of it and T[i-1, 0, False] =0 is the base case when we can’t do any business with 0 transactions.
Here is the modified recurrence:-

As we can see from above recurrence the only variables important to fill the current day are just one prev day and hence we can get rid of entire table and use them as variable. i.e.

Now if we observe the computation done for the variable T_it, this variable is just trying to save the max of negative price or in other words T_it variable is saving the minimum price so far seen with negative sign. Hence we can call T_it as negativemin variable.

But rather than keeping track of negativemin variable we can keep track of min variable and hence our recurrence will change its sign for the computation of T_f variable.

As we can see in the final recurrence, that we only need to keep track of min variable throughout our array pass and keep modifying t_f variable.

Whenever I use to solve problem like these and see such concise solution, I always wonder how could someone come up with such an easy solution and didn’t find any resources to see the derivation.
In next post I will start with other patterns and derivation for similar problems.
Please clap this post if you like it as it will motivate me to write similar blogs in future.
Peace!!!
References
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/#/description
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/