Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Count Hills and Valleys in an Array solution and explanation

EasyArray7 min read69.1% acceptanceUpdated 9 Apr 2026
Asked atGoogleMetaBloombergAmazonMicrosoft
Practise Count Hills and Valleys in an Array
11:00
Count Hills and Valleys in an Array | Simple Explanation | Leetcode 2210 | codestorywithMIKcodestorywithMIK · 11:00 · 6K viewsWatch on YouTube
9 more videos on this problem
  1. Count Hills and Valleys in an Array | Simple Explanation | Leetcode 2210 | codestorywithMIKcodestorywithMIK · 11:00 · 6K views
  2. 2210. Count Hills and Valleys in an Array || Leetcode Weekly Contest 285 || Leetcode 2210Bro Coders · 6:31 · 3K views
  3. Count Hills and Valleys in an Array | Leetcode 2210 | Easy | Contest 285 | 🔥🔥Coding Decoded · 3:52 · 1K views
  4. 2210. Count Hills and Valleys in an Array (Leetcode Easy)Programming Live with Larry · 4:31 · 953 views
  5. 2210. Count Hills and Valleys in an Array | Leetcode Daily - PythonLeetcode Daily · 5:50 · 818 views
  6. Leetcode 2210 - Count Hills and Valleys in an ArrayEmerald Bay · 7:52 · 812 views
  7. Daily Leetcode #1944: Jul 27, 2025 - 2210. Count Hills and Valleys in an ArrayProgramming Live with Larry · 4:39 · 691 views
  8. LeetCode - 2210. Count Hills and Valleys in an Array | Two Pointers Technique | JavaOrkhan Gasanov · 5:33 · 448 views
  9. Count Hills and Valleys in an Array | LeetCode 2210 | Java Code | Developer CoderDeveloper Coder · 10:22 · 292 views
  10. Count Hills and Valleys in an Array | LeetCode 2210 - Pythonimpoldev · 7:01 · 270 views

The 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 in nums.

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 <= 100
  • 1 <= nums[i] <= 100

Approach overview

Problem Overview: You’re given an integer array representing heights. A hill occurs when the current value is strictly greater than its nearest different neighbors, and a valley occurs when it is strictly smaller. Consecutive duplicates do not form new terrain changes, so they must be skipped when determining the previous and next values.

Approach 1: Linear Scan with Skip Duplicates (O(n) time, O(1) space)

This approach walks through the array once while ignoring consecutive duplicate values. The key insight is that duplicates should be treated as part of the same plateau, so you only compare the current number with the previous distinct value and the next distinct value. Iterate from index 1 to n-2, skipping duplicates using a loop until a different value appears. If nums[i] is greater than both neighbors, it forms a hill; if it is smaller than both, it forms a valley. Each element is processed at most once, so the time complexity is O(n) and the algorithm uses O(1) extra space.

This technique relies on simple comparisons and sequential iteration, making it ideal for problems focused on terrain patterns in arrays. It’s a common pattern when dealing with plateau-style data where duplicates distort local comparisons. The implementation is straightforward and works efficiently even for large inputs.

Approach 2: Two Pointers (O(n) time, O(1) space)

The two pointers strategy maintains a pointer to the previous distinct value while scanning forward with another pointer. As you iterate through the array, skip duplicate elements until the next different value appears. With pointers positioned at prev, curr, and next, check whether the current value forms a hill or valley. After evaluation, move the prev pointer forward to the last processed distinct value.

This method makes the duplicate skipping logic explicit and keeps comparisons clean. It still performs a single pass through the array, resulting in O(n) time complexity and O(1) auxiliary space. The approach is particularly readable when implementing terrain-style comparisons because each pointer clearly represents a structural role in the sequence.

Problems like this frequently appear in array traversal tasks where local patterns depend on neighboring values. Variants also show up alongside pointer-based traversal strategies such as two pointers or slope detection logic.

Recommended for interviews: The Linear Scan with Skip Duplicates approach is what most interviewers expect. It demonstrates that you understand how duplicates affect local comparisons and how to maintain constant space while scanning the array. Explaining the plateau issue first and then implementing the O(n) scan shows strong problem decomposition skills.

Approach 1: Approach 1: Linear Scan with Skip Duplicates

This approach involves iterating through the list while skipping consecutive duplicate values to identify hills and valleys. We only consider points as potential hills or valleys if their adjacent non-equal neighbors on both sides exist and fulfill the necessary conditions.

def countHillsAndValleys(nums):
    count = 0
    i = 1
    while i < len(nums) - 1:
        if (nums[i] > nums[i - 1] and nums[i] > nums[i + 1]) or (nums[i] < nums[i - 1] and nums[i] < nums[i + 1]):
            count += 1
            while i < len(nums) - 1 and nums[i] == nums[i + 1]:
                i += 1  # Skip duplicates
        i += 1
    return count

nums = [2, 4, 1, 1, 6, 5]
print(countHillsAndValleys(nums))
public class Solution {
    public int countHillsAndValleys(int[] nums) {
        int count = 0;
        for (int i = 1; i < nums.length - 1; i++) {
            if ((nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) ||
                (nums[i] < nums[i - 1] && nums[i] < nums[i + 1])) {
                count++;
                while (i < nums.length - 1 && nums[i] == nums[i + 1]) i++;  // Skip duplicates
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums = {2, 4, 1, 1, 6, 5};
        Solution sol = new Solution();
        System.out.println(sol.countHillsAndValleys(nums));
    }
}
#include <iostream>
#include <vector>
using namespace std;

int countHillsAndValleys(vector<int>& nums) {
    int count = 0;
    for (int i = 1; i < nums.size() - 1; ++i) {
        if ((nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) ||
            (nums[i] < nums[i - 1] && nums[i] < nums[i + 1])) {
            ++count;
            while (i < nums.size() - 1 && nums[i] == nums[i + 1]) ++i;  // Skip duplicates
        }
    }
    return count;
}

int main() {
    vector<int> nums = {2, 4, 1, 1, 6, 5};
    cout << countHillsAndValleys(nums);
    return 0;
}
function countHillsAndValleys(nums) {
    let count = 0;
    for (let i = 1; i < nums.length - 1; i++) {
        if ((nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) ||
            (nums[i] < nums[i - 1] && nums[i] < nums[i + 1])) {
            count++;
            while (i < nums.length - 1 && nums[i] === nums[i + 1]) i++;  // Skip duplicates
        }
    }
    return count;
}

const nums = [2, 4, 1, 1, 6, 5];
console.log(countHillsAndValleys(nums));
#include <stdio.h>

int countHillsAndValleys(int *nums, int numsSize) {
    int count = 0;
    for (int i = 1; i < numsSize - 1; i++) {
        if ((nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) ||
            (nums[i] < nums[i - 1] && nums[i] < nums[i + 1])) {
            count++;
            while (i < numsSize - 1 && nums[i] == nums[i + 1]) i++;  // Skip duplicates
        }
    }
    return count;
}

int main() {
    int nums[] = {2, 4, 1, 1, 6, 5};
    int size = sizeof(nums) / sizeof(nums[0]);
    printf("%d", countHillsAndValleys(nums, size));
    return 0;
}
using System;

public class Solution {
    public int CountHillsAndValleys(int[] nums) {
        int count = 0;
        for (int i = 1; i < nums.Length - 1; i++) {
            if ((nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) ||
                (nums[i] < nums[i - 1] && nums[i] < nums[i + 1])) {
                count++;
                while (i < nums.Length - 1 && nums[i] == nums[i + 1]) i++;  // Skip duplicates
            }
        }
        return count;
    }

    public static void Main(string[] args) {
        int[] nums = {2, 4, 1, 1, 6, 5};
        Solution sol = new Solution();
        Console.WriteLine(sol.CountHillsAndValleys(nums));
    }
}

The Python solution follows the same logic, iterating using a while-loop, which allows for conveniently skipping repeated values.

Complexity

Time Complexity: O(n), where n is the length of the input list.
Space Complexity: O(1) given that no additional structures are created.

Try this approach in the editor

Approach 2: Approach 2: Two Pointers

This approach employs two pointers to effectively manage non-equal comparisons and avoid redundant checks.

def countHillsAndValleys(nums):
    count = 0
    left = 0
    i = 1
    while i < len(nums) - 1:
        right = i + 1
        while right < len(nums) and nums[i] == nums[right]:
            right += 1
        if right < len(nums) and ((nums[i] > nums[left] and nums[i] > nums[right]) or
                                  (nums[i] < nums[left] and nums[i] < nums[right])):
            count += 1
        left = i
        i = right
    return count

nums = [2, 4, 1, 1, 6, 5]
print(countHillsAndValleys(nums))
public class Solution {
    public int countHillsAndValleys(int[] nums) {
        int count = 0, left = 0;
        for (int i = 1; i < nums.length - 1; i++) {
            int right = i + 1;
            while (right < nums.length && nums[i] == nums[right]) right++;
            if (right < nums.length &&
                ((nums[i] > nums[left] && nums[i] > nums[right]) ||
                 (nums[i] < nums[left] && nums[i] < nums[right]))) {
                count++;
            }
            left = i;
            i = right - 1;
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums = {2, 4, 1, 1, 6, 5};
        Solution sol = new Solution();
        System.out.println(sol.countHillsAndValleys(nums));
    }
}
#include <iostream>
#include <vector>
using namespace std;

int countHillsAndValleys(vector<int>& nums) {
    int count = 0, left = 0;
    for (int i = 1; i < nums.size() - 1; ++i) {
        int right = i + 1;
        while (right < nums.size() && nums[i] == nums[right]) ++right;
        if (right < nums.size() &&
           ((nums[i] > nums[left] && nums[i] > nums[right]) ||
            (nums[i] < nums[left] && nums[i] < nums[right]))) {
            ++count;
        }
        left = i;
        i = right - 1;
    }
    return count;
}

int main() {
    vector<int> nums = {2, 4, 1, 1, 6, 5};
    cout << countHillsAndValleys(nums);
    return 0;
}
function countHillsAndValleys(nums) {
    let count = 0;
    let left = 0;
    for (let i = 1; i < nums.length - 1; i++) {
        let right = i + 1;
        while (right < nums.length && nums[i] === nums[right]) right++;
        if (right < nums.length && 
           ((nums[i] > nums[left] && nums[i] > nums[right]) || 
            (nums[i] < nums[left] && nums[i] < nums[right]))) {
            count++;
        }
        left = i;
        i = right - 1;
    }
    return count;
}

const nums = [2, 4, 1, 1, 6, 5];
console.log(countHillsAndValleys(nums));
#include <stdio.h>

int countHillsAndValleys(int *nums, int numsSize) {
    int count = 0, left = 0;
    for (int i = 1; i < numsSize - 1; i++) {
        int right = i + 1;
        while (right < numsSize && nums[i] == nums[right]) right++;
        if (right < numsSize &&
            ((nums[i] > nums[left] && nums[i] > nums[right]) || (nums[i] < nums[left] && nums[i] < nums[right]))) {
            count++;
        }
        left = i;
        i = right - 1;
    }
    return count;
}

int main() {
    int nums[] = {2, 4, 1, 1, 6, 5};
    int size = sizeof(nums) / sizeof(nums[0]);
    printf("%d", countHillsAndValleys(nums, size));
    return 0;
}
using System;

public class Solution {
    public int CountHillsAndValleys(int[] nums) {
        int count = 0, left = 0;
        for (int i = 1; i < nums.Length - 1; i++) {
            int right = i + 1;
            while (right < nums.Length && nums[i] == nums[right]) right++;
            if (right < nums.Length &&
                ((nums[i] > nums[left] && nums[i] > nums[right]) ||
                 (nums[i] < nums[left] && nums[i] < nums[right]))) {
                count++;
            }
            left = i;
            i = right - 1;
        }
        return count;
    }

    public static void Main(string[] args) {
        int[] nums = {2, 4, 1, 1, 6, 5};
        Solution sol = new Solution();
        Console.WriteLine(sol.CountHillsAndValleys(nums));
    }
}

The Python solution equally employs two pointers to manage and skip duplicate checks, targeting non-equal neighbors directly.

Complexity

Time Complexity: O(n).
Space Complexity: O(1).

Try this approach in the editor

Approach 3: Traversal

We initialize a pointer j to point to the position with index 0, and then traverse the array in the range [1, n-1]. For each position i:

  • If nums[i] = nums[i+1], then skip.
  • Otherwise, if nums[i] is greater than nums[j] and nums[i] is greater than nums[i+1], then i is a peak; if nums[i] is less than nums[j] and nums[i] is less than nums[i+1], then i is a valley.
  • Then, we update j to i and continue to traverse.

After the traversal, we can get the number of peaks and valleys.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

function countHillValley(nums: number[]): number {
    let ans = 0;
    for (let i = 1, j = 0; i < nums.length - 1; ++i) {
        if (nums[i] === nums[i + 1]) {
            continue;
        }
        if (nums[i] > nums[j] && nums[i] > nums[i + 1]) {
            ans++;
        }
        if (nums[i] < nums[j] && nums[i] < nums[i + 1]) {
            ans++;
        }
        j = i;
    }
    return ans;
}
func countHillValley(nums []int) int {
	ans := 0
	for i, j := 1, 0; i < len(nums)-1; i++ {
		if nums[i] == nums[i+1] {
			continue
		}
		if nums[i] > nums[j] && nums[i] > nums[i+1] {
			ans++
		}
		if nums[i] < nums[j] && nums[i] < nums[i+1] {
			ans++
		}
		j = i
	}
	return ans
}
impl Solution {
    pub fn count_hill_valley(nums: Vec<i32>) -> i32 {
        let mut ans = 0;
        let mut j = 0;

        for i in 1..nums.len() - 1 {
            if nums[i] == nums[i + 1] {
                continue;
            }
            if nums[i] > nums[j] && nums[i] > nums[i + 1] {
                ans += 1;
            }
            if nums[i] < nums[j] && nums[i] < nums[i + 1] {
                ans += 1;
            }
            j = i;
        }

        ans
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Approach 1: Linear Scan with Skip Duplicates

Time Complexity: O(n), where n is the length of the input list.
Space Complexity: O(1) given that no additional structures are created.

Approach 2: Two Pointers

Time Complexity: O(n).
Space Complexity: O(1).

Traversal–

Complexity analysis

ApproachTimeSpaceWhen to Use
Linear Scan with Skip DuplicatesO(n)O(1)General case. Best approach when you need to detect hills and valleys while ignoring consecutive duplicates.
Two PointersO(n)O(1)When you want clearer control over previous, current, and next distinct values during traversal.

Frequently asked questions

Is Count Hills and Valleys in an Array easy or hard?

Count Hills and Valleys in an Array is classified as an Easy problem. The main challenge is handling consecutive duplicates correctly before checking hill or valley conditions. Once that edge case is handled, the algorithm becomes a straightforward single-pass array scan.

Count Hills and Valleys in an Array Python/Java solution

Both Python and Java implementations follow the same idea: iterate through the array, skip duplicates, and compare the current element with the previous and next distinct elements. The logic remains O(n) time and O(1) space across languages such as Python, Java, C++, C#, and JavaScript.

How to solve Count Hills and Valleys in an Array in O(n)?

Traverse the array while skipping consecutive duplicate values so that only distinct neighbors are compared. For each index, check if the value is greater than both neighbors (hill) or smaller than both (valley). Counting these conditions during a single pass gives an O(n) solution with constant space.

What is the best approach for Count Hills and Valleys in an Array?

The best approach is a linear scan that skips consecutive duplicates. While traversing the array, compare each element with the nearest distinct values on both sides to determine whether it forms a hill or valley. This method runs in O(n) time with O(1) extra space and handles plateau cases correctly.

Is Count Hills and Valleys in an Array asked at Google/Amazon/Meta?

Array traversal and local pattern detection problems like this appear in interviews at companies such as Amazon, Google, and Meta. While the exact problem may vary, the concept of identifying peaks, valleys, or slopes in arrays is a common interview pattern.

What data structure is used in Count Hills and Valleys in an Array?

The problem primarily uses arrays with simple iteration. No additional data structures are required because the solution only relies on comparing neighboring values and maintaining a few index variables.

What is the time complexity of Count Hills and Valleys in an Array?

The optimal solution runs in O(n) time because the array is scanned once while skipping duplicates. Each element is processed at most once, and only constant extra variables are used. Space complexity remains O(1).

Comments

Next problem · similarFind Peak ElementMedium
Now write it yourselfClose this page and solve Count Hills and Valleys in an Array in the editor, without looking.
Practise Count Hills and Valleys in an Array