Introduction
In this series of "Leetcode" posts I will publish solutions to leetcode problems. It is true that you can find most/lots of leetcode solutions on the web, but I will try to post my solutions to problems that are interesting or to problems for which the solutions out there are not well explained and deserve a better explanation.
The aim is to share knowledge, and that people who are studying, preparing for interviews, or just practicing, can become better at solving problems. Please feel free to comment if you have a suggestion or a different approach!
Problem link
Problem statement
You are given an array and you have to find hills and valleys.
The idea is simple yet a bit complex, I will just copy/paste from leetcode which is
already quite verbose but helps to fully understand the problem.
Example:
Input: nums = [2,4,1,1,6,5]
Output: 3
Explanation:
At index 0: There is no nonequal neighbor of 2 on the left, so index 0 is neither a hill nor a valley.
At index 1: The closest nonequal neighbors of 4 are 2 and 1. Since 4 > 2 and 4 > 1, index 1 is a hill.
At index 2: The closest nonequal neighbors of 1 are 4 and 6. Since 1 < 4 and 1 < 6, index 2 is a valley.
At index 3: The closest nonequal neighbors of 1 are 4 and 6. Since 1 < 4 and 1 < 6, index 3 is a valley, but note that it is part of the same valley as index 2.
At index 4: The closest nonequal neighbors of 6 are 1 and 5. Since 6 > 1 and 6 > 5, index 4 is a hill.
At index 5: There is no nonequal neighbor of 5 on the right, so index 5 is neither a hill nor a valley.
There are 3 hills and valleys so we return 3.
Solution
This problem despite being "easy" took me some time to solve.
I had to sleep over it to find an extremely quick solution next day :)
Sometimes you just gotta rest.
Important considerations
 One of the most challenging parts of this problem is the fact that you could have duplicates:
1,2,2,2,8 > This has one Hill
This means that you have to "ignore" the adjacent equal vales and only consider the values that are different
 Another important constraint or issue, is that at the beginning of the array you don't know if you are going up or down.
Approach 1
 At any point in time, you will be either "Up" or "Down"
 Except in the beginning, as you don't have previous value for the first value of the array
 If you are going UP and then go down, meaning you find that the next value is less than the current value , then that means you have found a Hill.
 If you are going DOWN and then go up, meaning you find that the next value is larger than the current value , then that means you have found a Valley.
public int countHillValleyWithFlag(int[] nums) {
int valleys = 0;
int hills = 0;
int index = 1;
// Find first nonrepeating value
while (index < nums.length && nums[index] == nums[index  1]) {
index++;
}
if (index == nums.length) return 0;
boolean isUp = nums[index] > nums[index  1];
while (index < nums.length) {
int cur = nums[index];
int prev = nums[index  1];
if (cur > prev) {
if (!isUp) {
hills++;
isUp = true;
}
} else if (cur < prev) {
if (isUp) {
valleys++;
isUp = false;
}
}
index++;
}
return valleys + hills;
}
 We have to find the first nonrepeating value, this is because we have to know if we are UP or DOWN, if the values are the same, we don't know this fact.
 Once we know if we are going UP or DOWN, then we can check:
 If current > prev && !isUP(down): If we were going DOWN and the current value is greater than previous, we have found a Valley */
 If current < previous && isUP: If we were going UP and the current value is less than previous, we have found a Hill /*\
Approach 2
 Notice that for a Hill or Valley we have neighbour values that should be different to the current value.
 Key fact : The surrounding values have both to be greater or less than the value in the middle.
 Picture this hill: 10, 30, 20
 Picture this valley: 30, 10, 50
 We have to find the neighbour/surrounding values. And if they comply to the abovementioned statements then we found a valley/hill.
public int countHillValleyNeighbours(int[] nums) {
int prev = nums[0];
int hills = 0;
int valleys = 0;
for (int i = 1; i < nums.length  1; i++) {
int cur = nums[i];
int next = nums[i + 1];
if (next != cur) {
if (prev > cur && next > cur) valleys++;
else if (prev < cur && next < cur) hills++;
prev = cur;
}
}
return hills + valleys;
}
We have to ignore similar values, for instance:
1,2,3,3,3,4,5At index 4, we cannot say "3" is the previous values, remember that we are looking for
values/neighbours that are different to the actual value.We basically want to simplify to this:
1,2,3,4,5So the actual neighbours of 3 are 2 and 4.

To do this we just have to be sure that the "next" value is different that the "current"
and then we can replace the old previous value with the current one.Complexity
Time complexity
 In both approaches we just have to go through the array one time Therefore:
 O(n) : Linear to the input size
Space complexity
 We don't make use of any other data structure. We simply use some variables. Therefore:
 O(1) Constant space, as it does not depend on the input size
Final comments:
This was a tricky task but fun to do it.
It is a good idea to analyze the requirements in concrete terms.
In this case: what it means a hill or a valley?
If you can put those into words then you already have an algorithm to solve it.
Top comments (0)