LeetCode #122: The Valleys and Peaks Approach
Tags: beginners, algorithms, arrays, ruby
Published: 2019-11-10 10:41:14

 ---
title: LeetCode #122: The Valleys and Peaks Approach
cover_image: https://thepracticaldev.s3.amazonaws.com/i/h3mufaxb9uuco0nxzjm9.png
published: true
description: I revisited a LeetCode problem with a different solution that made more sense. Though the newer solution is thicker and less pretty.
tags: #beginners, #algorithms, #arrays, #ruby
---

**SPOILER:** This post will go over this problem [122. Best Time to Buy and Sell Stock II](https://leetcode.com/problems/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:

```ruby
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:

```ruby
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:

```ruby
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:
![first iteration](https://thepracticaldev.s3.amazonaws.com/i/oc3st3khg4m753ueg7bj.png)

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:
![second iteration](https://thepracticaldev.s3.amazonaws.com/i/pyx8uz0vyrilxk8e773p.png)

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.