Stock Problem on Leetcode
I spend much time on completing a series of stock problem on leetcode. Some problem can be solved with greedy while others can be solved with dynamic programming. However, I ran into many challenges while defining the subproblems. Therefore, I would like to take a conclusion in this article, hope someone also try to solve these problems find this article helpful!
- 121. Best Time to Buy and Sell Stock
- 122. Best Time to Buy and Sell Stock II
- 123. Best Time to Buy and Sell Stock III
- 188. Best Time to Buy and Sell Stock IV
- 309. Best Time to Buy and Sell Stock with Cooldown
- 714. Best Time to Buy and Sell Stock with Transaction Fee
Pay attention! The writeup shown in this article won’t include exception handling!
121. Best Time to Buy and Sell Stock
In this problem, we can only make at most one transaction to find the max profit. In this series of problem, if we buy stock on the first day, it’s not necessary for us to sell on next day. We can choose one of the following days to get the max profit.
Idea: If we can only make one transaction, we should try to find biggest price gap which is
prices[n] - prices[m] for
m = n+1, n+2, ... the last day. Therefore, we use two variables:
mp to store the least price so far, and
max to store the biggest price gap so far.
If the biggest price gap for current price is bigger than max, then we can change it to be the max value. To the last day, we can get the max profit for making at most one transaction.
Luckily, this problem is at the easy level, and my writeup beats over 99% of submission on leetcode.
122. Best Time to Buy and Sell Stock II
In this problem, we can make many transactions as we can. Before coming up with idea, we need to figure out the strategy for this problem. Following is the visualization of prices:
There are two maps for
p1, p2, p3, p4 in above. How can we choose buy and sell for the max profit? If we look at the second picture, the max profit would be
(p2 - p1) + (p4 - p3) which is bigger than
(p4 - p1). If we look at the first picture, the max profit would be
(p2 - p1) + (p3 - p2) + (p4 - p3) which is equal to
(p4 - p1). In other words, we only need to consider one day for each time. If the unit price gap is positive, then we can add to the profit.
Idea: If the price on the second day is bigger than the first day, buy it on the first day and sell it on the second day. Add the price gap to the max profit.
Luckily, this problem is also at the easy level, and my writeup beats over 93% of submission on leetcode.
123. Best Time to Buy and Sell Stock III
In this problem, we can make at most two transactions. This is a classic DP problem. Following are several ways to define the subproblem:
dp[i][j]: the max profit for completing i transactions before day j. There are two cases on the jth day: 1. We do nothing on the jth day, so the profit remain the same. 2. We sell stock on the jth day, the possible day for us to buy such stock would be from 0 to (j-1). (We don’t need to consider the case of buying on jth day because it must decrease the profit.) Therefore, our max profit can be found from following:
$$ dp[i][j-1] $$
$$ dp[i-1] + prices[j] - prices $$
$$ dp[i-1] + prices[j] - prices $$
$$ … $$
$$ dp[i-1][j-1] + prices[j] - prices[j-1] $$
The first one is the case 1, we do nothing on jth day, which means we already complete i transactions on (j-1)th day. From the second one to the last one is for case 2. Following is the source code:
However, this solution only beats over 6% of submission on leetcode because of high time complexity: O(n^2k). After reading the discussion board, I think I can swap two loops to make it faster:
The reason for being faster is that the first one switches to the next loop each time for O(n) while the next one switches to the next loop each time for O(1). However, I am still not satisfied with the solution.
dp[time], or even just a variable!
Idea: If we define subproblem to be
dp[i]: maxprofit got until ith day, it would be hard to define first transaction and the second transaction. However, we don’t need to define array for maxprofit got until each transactions. There are four states in this problem, buy 1nd stock -> sell 1nd stock -> buy 2nd stock -> sell 2nd stock. We eager to get the max profit on each state. For each state, we have two choices, one is remain the same, the other one is do the operation, find the choice for the bigger profit. Following is the source code:
Take a look at the line 5, we eager to find the max profit for buying stock on first transaction. Therefore, our two choices are: 1. remain the same as previous, which is
0 - prices[i], which is
Interesting, with this solution, we can beat over 92% of submission on leetcode.
188. Best Time to Buy and Sell Stock IV
In this problem, we can make at most k transactions. It is very similiar to the previous problem, so I use the same idea:
sell[k]. Following is the source code:
sell are defined for the convenience, one reason is for easy understanding, another reason is for convenience. Everything seems perfect; however, there are a trap hidden in this problem. I found that if k is so big, memory time limit would be exceeded. In fact, if
k*2 >= prices.length, we can reduce our time complexity from
O(n) because we can make transaction on each day, then the problem is same as <122. Best Time to Buy and Sell Stock II>.
With this solution, we can beat over 95% of submission on leetcode.
309. Best Time to Buy and Sell Stock with Cooldown
There is no limit times for transactions, but there must be a cooldown day after each sell operations.
Idea: The problem is different from the previous one which is limited by k times. Therefore, I define the subproblem as
buy[i]: max profit for holding stock on ith day and
sell[i]: max profit for not holding stock on ith day. Following is the source code:
First, there are two possibilities for holding stock on today: One is already holding on yesterday, which is
buy[i-1]. Second is not holding on two days before and buying on today, which is
sell[i-2] - prices[i]. However, index need to be larger than 1.
Second, there are also two possibilities for not holding stock on today: One is already not holding on yesterday, which is
sell[i-1]. Second is hold on yesterday and sell on today, which is
buy[i-1] + prices[i].
However, this solution only beats over 61% of submission on leetcode.
not_holdcan help more people figure it out.
But, I am still not satisfied with current solution. Dig into the detail of the solution above, and I found that we can just use several variables instead of using arrays.
buy[i]is only related with
sell[i]is only related with
Idea: For the purpose of better understanding, I would like to change name to
not_holdnow. The relationship between
hold[i-1]can be defined as updating the value if bigger, and same for
not_hold. In addition, we need another variable to store the
sell[i-2], which is called as
Following is my explanation for the solution above:
Nice, now our solution beats 100% of submission on leetcode!!
714. Best Time to Buy and Sell Stock with Transaction Fee
There is no limit times for transactions, but there is transaction fee with each transaction after sell the stock. Therefore, I would combine operation of sell and paying for fee to one state.
Idea: I use the same idea for array in the previous problem.
However, I am not satisfied with my solution because it only beats over 53% of submission on leetcode. Therefore, I would make a same change as previous problem to my solution. Following is my source code:
Now, my solution beats over 94% of submission on leetcode!
When we run into a problem, the first thing we should do is to draw a state machine map. How many states does the problem have? What is the relationship between these states? Then how to define subproblem? Which kind of subproblem can lead us to a convenient solution? Don’t pursuit the most efficient solution at first, but implement with the solution which is easy to understand at first, and try to simplify our first solution to get higher grade.
To summarize this series of problems, I find that if number of transactions is limited, we need to define subproblem of each time transaction, e.g.
sellk. Also we can turn it back to the problem of arbitrary k if k is bigger then prices.length/2! If k is arbitrary, we can use
not_holdi where i is the day of price to define the subproblem, then update the max value of
not_hold on each day.
When I read through the solution on discussion board, some solution comes up with the most votes; however, it is hard for me to understand. Therefore, I think solution is not absolute, but we should choose presonally the one which is easy to understand for us.