Best Time to Buy and Sell Stock II

Coding Interviews Best Time to Buy and Sell Stock II (LeetCode) question and explanation.

This question is a commonly asked by the following companies: Facebook, Amazon, Microsoft, Adobe, Alibaba, and Bloomberg.

Problem description: Say you have 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 (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 1:
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Intuition behind solution: Find each place where we can make a profit. Therefore we are simply comparing the ith price with the i + 1 price at every index and buy and selling if the ith price is less than the i + 1 price. If this is the case, we should buy on the current day and a sell the next day which yields a profit of prices[i + 1] - prices[i].

My Desk Setup

[jacobburstyn]

The solution is correct not because you are selling on the days which are higher than the previous day but rather the loop adds up all potential gains. So if for example the array is [5, 7, 100] the best is to buy on day 1 where the price is 5 and sell on day three where the price is 100. Kevin's solution adds the gains of day one to day two with the gains of day two to day three. Even if selling and re buying on the same day is not allowed this is still correct.

[OverLordOfDardWorld]

wow I over thought this question so hard, you don't even want to know what I was attempting. Thank you so much Kevin!!

[Dylan-ohii]

This one took me several minutes to understand why this solution works. Rather than thinking of why you would need to recurse to get the optimal profit, think more about how this solution assumes that in the event of continuous growth, you bought and sold on the same day, as if that day did not occur (from a profit perspective).

[jainayak]

this is LITERALLY the code I wrote! Line for line, except, my if condition was (prices[i] < prices[i+1]). I paused your video and read a couple of comments, saying they couldn't believe it was a simple solution, and went back and started thinking along those lines and arrived at the same code! I feel validated .. you're awesome dude!

[mrginn]

I feel like an idiot after watching your solution. Thanks man!

[Jellies]

Thank you for this! Couldn't understand this problem even after reading the discussions!

[shreelakshmijoshi]

Thank you very much ! I couldn't understand the solution even by looking at the leetcode solution.

[quangvo]

This is the perfect solution. Dynamic Programming

[aadishpadmonkar]

Thanks @Kevin Naughton Jr, I was overthinking this problem to a great extent .

[nareshnepal]

hey kevin just adding a bit of complexity i personally faced... please get the max profit with minimum transactions..cheers!!

[swethajayaram]

@Kevin Naughton Jr. I think the solution is incorrect. In the description, Example 1 we bought the stock on 1st day and sold them on 2nd day and also bought on 4th day and sold them on 5th day. In example 2, we bought the shares on 1st and sold them on 5th day. But 'if' statement in the for loop would not wait if the 3rd is highest and gives you more profit. Or I am not sure if buying and selling on the same day has given you that advanctage to ignore this. I guess that's what most of the viewers are confused about.

[revanthbomma]

edge case might also also need to consider prices.length == 1

[metronadsouza]

Hi Kevin ..can you solve the Buy and sell stock with K transactions ? thanks

[YameenYasin]

Thanks Kevin for this perfect solution ...


Below is explanation why it works, if it helps anyone.. :)


As the problem says You may not engage in multiple transactions at the same time. Which means we cannot buy again before we sell..
Lets try to understand why this code works by using the below example


7, 2, 1, 10


If we buy on day 1 and sell on day 2 -> We are at Loss. So not an option
If we buy on day 2 and sell on day 3 -> We are again at Loss ... Here some people will think why not buy on Day 2 and Sell on Day 4 ... The reason is simple, day 3 price is already less than Day 2 price, so we will buy on day 3 and sell on day 4 which will give a Profit of 9..


7, 2, 3, 10


If we buy on day 1 and sell on day 2, we are at loss
If we buy on day 2 and sell on day 3, we can make a profit of 1
On day 3, we can sell the stock and again buy it for selling on day 4 to make a profit of 7
Total profit = 8


Let me know if this makes sense.. :)

[ellisakhoja]

Hey Kevin, Can you make video for Best Time to Buy and Sell Stock III?

[thybliss]

I understand this solution works but don't know for some reason could not understand reasoning behind it. For me intuitively the recursive solution makes more sense (it's in the leetcode solution) but I'm having hard time understanding the implementation - mainly with the working variables. If you understand the recursive solution could you please make a video for that?

[a.yashwanth]

What does buy one and sell one share of stock multiple times mean?
1 4 6
So buy 1 and sell at 4 for profit 3, sell again at 6 for profit of 5(cuz it's mentioned buy one and sell multiple times)?
But question also says you can't buy stock again befor you sell?
I don't understand.

[rajashreeswami]

Nice Video, can you create video on BEST TIME TO BUY AND SELL STOCK III

[sharinganuser]

this is just simplification of actual we can buy multiple stock...nd at any kth day the max profit we can have.

[Philson]

Bro. Did you not look at example 2? You need to compare with more than just the next day?