BebopVinh

Posted on

# LeetCode #122: The Valleys and Peaks Approach

SPOILER: This post will go over this problem 122. Best Time to Buy and Sell Stock II

Two months ago, a cohort mate and I decided to tackle this problem. Our first impression was that it shouldn't be too hard. We were in over our heads.
Here's my best initial solution, which didn't work at all:

``````def max_profit(prices)
start = prices.shift
last = prices.length - 1
#default case which returns 0 if prices only decreases over time
if prices.all? {|n| n < start}
return 0
end
min, max = start, 0
prices.each do |n|
if n < start
min = n
elsif n > max
max = n
end
end
end
``````

It must have been at least 2 hours, and we were both frustrated. I caved and looked at the "Solution" tab and went for the shortest, cleanest chunk of code I saw:

``````def max_profit(prices)
i = 1
profit = 0
while i < prices.length
if (prices[i] > prices[i-1])
profit += prices[i] - prices[i - 1]
end
i += 1
end
profit
end
``````

It's a clean `while` loop. But, it wasn't very intuitive to me. The problem is not asking to report the days where it's best to buy and sell stock, so this solution works. All it does is go through all the numbers in the array, then anytime it goes from a lower to a higher number, it counts that as profit. The way the problem is phrased, this solution is just not the first thing I would think of.

This week, a few other cohort mates decided to give this problem a try. And, I decided to look at another approach in the "Solution" tab. This time, dealing with valleys and peaks:

``````def max_profit(prices)
i, max = 0, 0
valley = prices.first
peak = prices.first
last = prices.length - 1

while i < last
while (i < last && prices[i] >= prices[i + 1])
i+= 1
end
valley = prices[i]
while (i < last && prices[i] <= prices[i + 1])
i += 1
end
peak = prices[i]
max += peak - valley
end
max
end
``````

Here's my crappy chart with annotation to try and explain this solution:

At first glance, I thought this was O( N^2 ) in time-complexity, because there are loops nested in a loop. But, a closer look will show that the counter is incremented via the nested loop. The outer loop picks up from where the second inner loop `while (i < last && prices[i] <= prices[i + 1])` ends. That means the whole thing traverse throug the array only once. So, it's O(N) for time-complexity.

This solution makes more sense. The outer loop makes sure the pointer/counter keeps going until the end of the graph. The first inner loop looks for a valley (a number right before the price starts increasing). The second inner loop will start afterwards. This one looks for a peak (a number right before the price starts decreasing). Once it has this, it adds the difference to the `max` profit. The loop ends at the tail of the array.

Here's the second iteration through the graph:

After this, the outer loop will restart at index 4. It will find a valley at index 5, but no peak. Therefore, there's nothing else added to the profit.