Count Hills and Valleys in an Array
EasyUpdated: Jul 27, 2025
Practice on:
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
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
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 <= 1001 <= 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
- Iterate through the array from index 1 to n-1.
- Skip if the current value is the same as the previous (part of the same hill/valley).
- Find the closest non-equal neighbor to the left (
left) and right (right). - If both neighbors exist, check if the current value is greater than both (hill) or less than both (valley).
- Count each hill or valley only once.
Code
C++
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;
}
};
Go
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
}
Java
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;
}
}
Kotlin
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
}
}
Python
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
Rust
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
}
}
TypeScript
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.