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.