Problem

You are given a 0-indexed integer array nums. An index i is part of a hill in nums if the closest non-equal neighbors of i are smaller than nums[i]. Similarly, an index i is part of a valley in nums if the closest non-equal neighbors of i are larger than nums[i]. Adjacent indices i and j are part of the same hill or valley if nums[i] == nums[j].

Note that for an index to be part of a hill or valley, it must have a non-equal neighbor on both the left and right of the index.

Return the number of hills and valleys innums.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
Input: nums = [6,6,5,5,4,1]
Output: 0
Explanation:
At index 0: There is no non-equal neighbor of 6 on the left, so index 0 is neither a hill nor a valley.
At index 1: There is no non-equal neighbor of 6 on the left, so index 1 is neither a hill nor a valley.
At index 2: The closest non-equal neighbors of 5 are 6 and 4. Since 5 < 6 and 5 > 4, index 2 is neither a hill nor a valley.
At index 3: The closest non-equal neighbors of 5 are 6 and 4. Since 5 < 6 and 5 > 4, index 3 is neither a hill nor a valley.
At index 4: The closest non-equal neighbors of 4 are 5 and 1. Since 4 < 5 and 4 > 1, index 4 is neither a hill nor a valley.
At index 5: There is no non-equal neighbor of 1 on the right, so index 5 is neither a hill nor a valley.
There are 0 hills and valleys so we return 0.

Constraints

  • 3 <= nums.length <= 100
  • 1 <= nums[i] <= 100

Solution

Method 1 – Robust Single Pass with Skipping Duplicates

Intuition

To accurately count hills and valleys, we need to compare each element to its closest non-equal neighbors on both sides. We skip consecutive duplicates to avoid counting the same hill or valley multiple times. The key is to ensure both left and right non-equal neighbors exist before making the comparison.

Approach

  1. Iterate through the array from index 1 to n-1.
  2. Skip if the current value is the same as the previous (part of the same hill/valley).
  3. Find the closest non-equal neighbor to the left (left) and right (right).
  4. If both neighbors exist, check if the current value is greater than both (hill) or less than both (valley).
  5. Count each hill or valley only once.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int countHillValley(vector<int>& nums) {
        int ans = 0, n = nums.size();
        for(int i = 1; i < n; i++){
            if(nums[i] == nums[i-1]) continue; // same hill or valley
            int left = i - 1, right = i + 1;
            while(left >= 0 && nums[left] == nums[i]) left--;
            if(left < 0) continue; // no left neighbour found
            while(right < n && nums[right] == nums[i]) right++;
            if(right == n) continue; // no right neighbour found
            if(nums[left] < nums[i] && nums[right] < nums[i]) ans++;
            else if(nums[left] > nums[i] && nums[right] > nums[i]) ans++;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func countHillValley(nums []int) int {
    ans, n := 0, len(nums)
    for i := 1; i < n; i++ {
        if nums[i] == nums[i-1] {
            continue // same hill or valley
        }
        left, right := i-1, i+1
        for left >= 0 && nums[left] == nums[i] {
            left--
        }
        if left < 0 {
            continue // no left neighbour found
        }
        for right < n && nums[right] == nums[i] {
            right++
        }
        if right == n {
            continue // no right neighbour found
        }
        if nums[left] < nums[i] && nums[right] < nums[i] {
            ans++
        } else if nums[left] > nums[i] && nums[right] > nums[i] {
            ans++
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int countHillValley(int[] nums) {
        int ans = 0, n = nums.length;
        for(int i = 1; i < n; i++){
            if(nums[i] == nums[i-1]) continue; // same hill or valley
            int left = i - 1, right = i + 1;
            while(left >= 0 && nums[left] == nums[i]) left--;
            if(left < 0) continue; // no left neighbour found
            while(right < n && nums[right] == nums[i]) right++;
            if(right == n) continue; // no right neighbour found
            if(nums[left] < nums[i] && nums[right] < nums[i]) ans++;
            else if(nums[left] > nums[i] && nums[right] > nums[i]) ans++;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    fun countHillValley(nums: IntArray): Int {
        var ans = 0
        val n = nums.size
        for (i in 1 until n) {
            if (nums[i] == nums[i-1]) continue // same hill or valley
            var left = i - 1
            var right = i + 1
            while (left >= 0 && nums[left] == nums[i]) left--
            if (left < 0) continue // no left neighbour found
            while (right < n && nums[right] == nums[i]) right++
            if (right == n) continue // no right neighbour found
            if (nums[left] < nums[i] && nums[right] < nums[i]) ans++
            else if (nums[left] > nums[i] && nums[right] > nums[i]) ans++
        }
        return ans
    }
}
 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: list[int]) -> int:
        ans, n = 0, len(nums)
        for i in range(1, n):
            if nums[i] == nums[i-1]:
                continue # same hill or valley
            left, right = i-1, i+1
            while left >= 0 and nums[left] == nums[i]:
                left -= 1
            if left < 0:
                continue # no left neighbour found
            while right < n and nums[right] == nums[i]:
                right += 1
            if right == n:
                continue # no right neighbour found
            if nums[left] < nums[i] and nums[right] < nums[i]:
                ans += 1
            elif nums[left] > nums[i] and nums[right] > nums[i]:
                ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
impl Solution {
    pub fn count_hill_valley(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut ans = 0;
        for i in 1..n {
            if nums[i] == nums[i-1] {
                continue; // same hill or valley
            }
            let mut left = i as i32 - 1;
            let mut right = i + 1;
            while left >= 0 && nums[left as usize] == nums[i] {
                left -= 1;
            }
            if left < 0 {
                continue; // no left neighbour found
            }
            while right < n && nums[right] == nums[i] {
                right += 1;
            }
            if right == n {
                continue; // no right neighbour found
            }
            if nums[left as usize] < nums[i] && nums[right] < nums[i] {
                ans += 1;
            } else if nums[left as usize] > nums[i] && nums[right] > nums[i] {
                ans += 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    countHillValley(nums: number[]): number {
        let ans = 0, n = nums.length;
        for (let i = 1; i < n; i++) {
            if (nums[i] === nums[i-1]) continue; // same hill or valley
            let left = i - 1, right = i + 1;
            while (left >= 0 && nums[left] === nums[i]) left--;
            if (left < 0) continue; // no left neighbour found
            while (right < n && nums[right] === nums[i]) right++;
            if (right === n) continue; // no right neighbour found
            if (nums[left] < nums[i] && nums[right] < nums[i]) ans++;
            else if (nums[left] > nums[i] && nums[right] > nums[i]) ans++;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the array, for a single pass.
  • 🧺 Space complexity: O(1), only a constant amount of space is used.