Algorithm Practice (Part 2)
In this week’s edition of Algorithm Practice, I’ll be going over a tricky problem that I encountered in a take home code challenge. Here is the description of the requirements for the algorithm as it was shown to me:
Explanation of the Problem
In essence, the input of a function is an array of numbers, and I need to return how many hills (or peaks) and valleys there are. If the input is [1, 4, 2] it would return 3 because the 1 is a valley, the 4 is a peak, and the 2 is another valley. If the input is [1, 1, 4, 4] it would return 2 because the two 1’s are a valley and the two 4’s are a peak.
Getting to the Solution
Edge Case
First off, we’ll start with the edge case logic. We know that the array could only have one number and that it is possible for all the numbers in the array to be the same based on the description above. In both of these cases, we’ll want to return 1 since there will be one peak/valley. Here’s a code snippet with the logic to check this:
The .every() function in JavaScript is a way to check that all elements in the array pass the test that written within the method. In this case, it is iterating over every number in the A array to see if it is the same as A[0]. The .every() function always returns a boolean value.
A few examples of arrays that will satisfy this edge case are, [1, 1, 1, 1], [5], [-100, -100, -100].
Base Case
Now that that’s taken care of, we’ll move on to handling the rest of the cases. To start, I initialize a variable called counter to keep track of how many peaks and valleys there are. It is created with the value of 2 because if the above edge case isn’t met, the return value will always be 2 or greater; if the array.length is greater than 1 and all the numbers in the array aren’t the same, the amount of peaks and valleys has to be 2 or more.
I am also creating a variable that is called pv (stands for peaks/valleys), and I don’t assign it a value on its initialization. It will soon be defined as a boolean once we get to the next section, with true indicating that it’s a peak, and false meaning that it’s a valley.
Here’s where we’re at so far:
Determining the Initial Value of pv
Now we need to find out if the first number(s) in the array are a peak or a valley. I will iterate through the array until I get to a number that is either greater than or less than the number before it.
It’s not necessary to loop through the whole array, since we only need enough information to give pv its initial value. I use break here to end the for loop once the conditional is met, and if A[i] is great than A[i + 1] then it is a peak (true) and if A[i] is less than A[i + 1] then it is a valley (false).
Using the Value of pv
Now that we know if pv is a peak (true) or a valley (false), we can use this knowledge to loop through the array and count how many of them there are. I’ll use a regular for loop and have a few nested conditionals within it. If it’s a peak and if A[i] is greater than A[i + 1] (which means that we’ve reached the end of a peak), I’ll increment the counter variable by 1 and reverse the value of pv to the opposite of what it was (in this case true → false). And vice versa if it is a valley. Here is the code:
Full Solution
Now that we have all the different pieces that we’ll need, let’s look at it all together!
Don’t forget to return something at the end! In this case I return the counter variable because the problem asked for an integer to be returned (the total number of peaks and valleys).
Hopefully this is helpful and happy coding to you!
