Leetcode: 2210. Count Hills and Valleys in an Array

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

Count hills and valleys

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 non-equal neighbor of 2 on the left, so index 0 is neither a hill nor a valley.
At index 1: The closest non-equal neighbors of 4 are 2 and 1. Since 4 > 2 and 4 > 1, index 1 is a hill.
At index 2: The closest non-equal neighbors of 1 are 4 and 6. Since 1 < 4 and 1 < 6, index 2 is a valley.
At index 3: The closest non-equal 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 non-equal neighbors of 6 are 1 and 5. Since 6 > 1 and 6 > 5, index 4 is a hill.
At index 5: There is no non-equal 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 non-repeating 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 non-repeating 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 above-mentioned 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,5

• At 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,5

• So 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.