Problem 6.7 Buying Stock Twice Variant

#1

Hi,

The variant of Problem 6.7 asks us to solve the problem of buying and selling stock twice using only O(n) time and O(1) space. There’s an easy solution using O(n^2) time and O(1) space, but I can’t seem to get the time complexity down to O(n). Would you be able to provide a hint?

Thanks,

0 Likes
#2

Hey @gauss,

The hint to this approach, in my opinion, is that using the approach of once, but adding two more variables to store the states after the first time and sell, say the most can earn after one buy and one sell and another buy, and the other variable is the most can earn after two buys and sells.

0 Likes
#3

see https://discuss.leetcode.com/topic/39751/my-explanation-for-o-n-solution/6

0 Likes
#4

The key to getting a lot of the “array crawl” type problems down to O(n) time is to reuse computations that you’ve already done, so you may want to allocate some extra space to store the things you’ve already calculated as you pass through the array.

Next, examine the reason why you wouldn’t be able to continue looking for sell prices after an initial buy sell sequence, and how you may get around this.

0 Likes