Count Hills and Valleys in an Array

We are dealing with an array of numbers, where some numbers could be identical to others, i.e., duplicates. These duplicates can sometimes make it more challenging to identify the hills (peaks) and valleys (troughs) in our data.

To tackle this problem, we use two pointers, typically called i and j. You can think of a pointer as an indicator or a marker at a specific position in our array.

Now, let’s understand how these pointers help us.

1. The i pointer: This is our main pointer that goes through every number in the array, one by one, from the start to the end.

2. The j pointer: This is our second pointer that we use to remember the last non-duplicate number we’ve encountered. We only move j when we encounter a new unique number that forms a hill or a valley.

Here’s how the process works:

We start at the beginning of the array. Both i and j are at the same position. As i moves ahead, j stays where it is until i encounters a hill or a valley. At that moment, we move j to the current position of i. This way, j always points to the starting position of the most recent hill or valley. This is beneficial as it lets us effectively ignore any duplicate numbers when identifying new hills and valleys.

So, by using this two-pointer approach, we can smoothly navigate the array, accurately identifying all the hills and valleys, while correctly handling any duplicate numbers.

Whiteboard version:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def countHillValley(self, nums):
        res = 0
        i = 1
        j = 0

        while i < len(nums) - 1:
            if (nums[j] < nums[i] and nums[i] > nums[i + 1]) or \
               (nums[j] > nums[i] and nums[i] < nums[i + 1]):
                res += 1
                j = i
            i += 1

        return res

Python beginner friendly version:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def countHillValley(self, nums):
        n = len(nums)
        last_num = nums[0]
        hills = 0
        valleys = 0

        for i in range(1, n-1):
            if nums[i] == last_num:
                last_num = nums[i]
                continue

            if nums[i] > last_num and nums[i] > nums[i+1]:
                hills += 1
                last_num = nums[i]
            elif nums[i] < last_num and nums[i] < nums[i+1]:
                valleys += 1
                last_num = nums[i]

        return hills + valleys

It iterates over the list, checking for peaks (hills) and troughs (valleys), then returns the sum of the two.